3 This file is part of the ARM-Crypto-Lib.
4 Copyright (C) 2006-2010 Daniel Otte (daniel.otte@rub.de)
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 q[ 0] = (+ h[ 5] - h[ 7] + h[10] + h[13] + h[14]);
21 q[ 3] = (+ h[ 8] - h[10] + h[13] + h[ 0] - h[ 1]);
22 q[ 6] = (- h[11] + h[13] - h[ 0] - h[ 3] + h[ 4]);
23 q[ 9] = (+ h[14] + h[ 0] - h[ 3] + h[ 6] - h[ 7]);
24 q[12] = (+ h[ 1] + h[ 3] - h[ 6] - h[ 9] + h[10]);
25 q[15] = (- h[ 4] - h[ 6] - h[ 9] + h[12] + h[13]);
26 q[ 2] = (+ h[ 7] + h[ 9] - h[12] + h[15] + h[ 0]);
27 q[ 5] = (+ h[10] - h[12] + h[15] - h[ 2] + h[ 3]);
28 q[ 8] = (+ h[13] - h[15] + h[ 2] - h[ 5] - h[ 6]);
29 q[11] = (- h[ 0] - h[ 2] - h[ 5] + h[ 8] + h[ 9]);
30 q[14] = (+ h[ 3] - h[ 5] + h[ 8] - h[11] - h[12]);
31 q[ 1] = (+ h[ 6] - h[ 8] + h[11] + h[14] - h[15]);
32 q[ 4] = (+ h[ 9] - h[11] - h[14] + h[ 1] + h[ 2]);
33 q[ 7] = (- h[12] - h[14] + h[ 1] - h[ 4] - h[ 5]);
34 q[10] = (+ h[15] - h[ 1] - h[ 4] - h[ 7] + h[ 8]);
35 q[13] = (+ h[ 2] + h[ 4] + h[ 7] + h[10] + h[11]);
39 [ '+5', '-7', '+10', '+13', '+14'],
40 [ '+8', '-10', '+13', '+0', '-1'],
41 [ '-11', '+13', '-0', '-3', '+4'],
42 [ '+14', '+0', '-3', '+6', '-7'],
43 [ '+1', '+3', '-6', '-9', '+10'],
44 [ '-4', '-6', '-9', '+12', '+13'],
45 [ '+7', '+9', '-12', '+15', '+0'],
46 [ '+10', '-12', '+15', '-2', '+3'],
47 [ '+13', '-15', '+2', '-5', '-6'],
48 [ '-0', '-2', '-5', '+8', '+9'],
49 [ '+3', '-5', '+8', '-11', '-12'],
50 [ '+6', '-8', '+11', '+14', '-15'],
51 [ '+9', '-11', '-14', '+1', '+2'],
52 [ '-12', '-14', '+1', '-4', '-5'],
53 [ '+15', '-1', '-4', '-7', '+8'],
54 [ '+2', '+4', '+7', '+10', '+11']
58 $stat_location=Hash.new
61 if s2.to_i.abs<s1.to_i.abs
67 idx = 0 if s1[0].chr=='+' && s2[0].chr=='+'
68 idx = 1 if s1[0].chr=='+' && s2[0].chr=='-'
69 idx = 2 if s1[0].chr=='-' && s2[0].chr=='+'
70 idx = 3 if s1[0].chr=='-' && s2[0].chr=='-'
71 puts "ERROR in idx" if idx==nil
72 if $stat[(s1[1..-1]+','+s2[1..-1])]==nil
73 $stat[(s1[1..-1]+','+s2[1..-1])] = [0,0,0,0]
74 $stat_location[(s1[1..-1]+','+s2[1..-1])] = i.to_s()
76 $stat_location[(s1[1..-1]+','+s2[1..-1])] += ','+i.to_s()
78 $stat[(s1[1..-1]+','+s2[1..-1])][idx]+= 1
86 r=1 if vb.find_index(p)
92 r=2 if vb.find_index(p)
98 def reg_empty(map, reg, from, to)
99 (from..to).each do |x|
100 return false if(map[x][reg])
105 def reg_set(map, reg, from, to, value)
106 (from..to).each do |x|
112 def print_reg_map(map, regs, length, indent=0)
113 (regs-1).downto(0) do |r|
114 print ' '*indent+'r'+r.to_s
115 print ' '*(2+(2-r.to_s.length))
117 (0..(length-1)).each do |x|
121 print map[x][r] if map[x][r].class == String
122 print map[x][r].to_s(36) if map[x][r].class == Fixnum
129 def reg_map(steps, length)
131 map = Array.new(length)
132 (0..(length-1)).each {|x| map[x]=Array.new}
135 a = step[2].split(',').collect { |x| x.to_i}
139 while(reg_empty(map,reg,from,to)==false)
142 reg_set(map, reg, from, to, step[3])
143 max_reg=reg if reg>max_reg
148 def word_to_steps(word, list)
161 def print_collision_map(collisions, length)
163 (0..(length-1)).each {|x| print ('A'[0]+x).chr+' '}
164 (0..(length-1)).each do |y|
165 print "\n"+('A'[0]+y).chr+' '
166 (0..(length-1)).each do |x|
167 if(collisions.find_index(('A'[0]+x).chr+('A'[0]+y).chr)) or
168 (collisions.find_index(('A'[0]+y).chr+('A'[0]+x).chr))
178 def check_collision(word, lut)
179 (0..(lut.length-1)).each do |i|
181 return true if word&lut[i]!=0
187 $bitcount_lut = Array.new(65536)
189 def bits_set_simple(x)
198 def init_bitcount_lut
199 (0..(2**4-1)).each {|x| $bitcount_lut[x] = bits_set_simple(x)}
200 ((2**4)..(2**8-1)).each {|x| $bitcount_lut[x] = bits_set(x, 4)}
201 ((2**8)..(2**16-1)).each {|x| $bitcount_lut[x] = bits_set(x, 8)}
204 def bits_set(x, length=16)
207 r += $bitcount_lut[x&(2**length-1)]
213 def decode_word(word)
226 def generate_c_code(fout, func, optimizations=[], reg_map=[], use_map=[])
230 opt_table = Array.new
231 optimizations.each do |opt|
232 opt_steps = opt[2].split(',')
233 opt_steps.collect! {|x| x.to_i}
234 opt_steps.each do |step|
235 reg_a = opt[0].split(',')[0]
236 reg_b = opt[0].split(',')[1]
237 sign_a = '+' if func[step].find_index('+'+reg_a)
238 sign_a = '-' if func[step].find_index('-'+reg_a)
239 sign_b = '+' if func[step].find_index('+'+reg_b)
240 sign_b = '-' if func[step].find_index('-'+reg_b)
243 if step==opt_steps[0]
248 while opt_table[opt_steps[0]][i][4]!=reg_a || opt_table[opt_steps[0]][i][5]!=reg_b
251 if(sign_a==opt_table[opt_steps[0]][i][0])
257 free = true if step==opt_steps[-1]
258 reg_number = reg_map[step].find_index(opt[3])
259 reg_name = sprintf("tr%d", reg_number)
260 opt_table[step] = Array.new if opt_table[step]==nil
261 opt_table[step] << [sign_a, sign_b, sign_out, reg_name, reg_a, reg_b, set, free]
264 (0..(func.length-1)).each do |i|
265 fout.printf("q[%2d] = ", out_idx)
266 out_idx = (out_idx+out_interval)%out_modulus
271 opt_table[i].each do |opt|
272 skip = 1 if opt[4]==j[1..-1] or opt[5]==j[1..-1]
275 fout.printf("%st[%2d] ", j[0].chr, j[1..-1].to_i) if skip==0
276 use_map[-1] << j[1..-1].to_i if skip==0
279 opt_table[i].each do |opt|
280 fout.print(opt[2]+'('+opt[3])
282 fout.printf('=%st[%2d]%st[%2d]',opt[0],opt[4].to_i,opt[1],opt[5].to_i)
283 use_map[-1] << opt[4].to_i
284 use_map[-1] << opt[5].to_i
295 return nil if self.length==0
299 if(self[i]!=nil && max<self[i])
309 def calculate_load_pressure(use_map, use_locations, regs, steps)
311 reg_map = Array.new(steps)
312 (0..(reg_map.length-1)).each{|i| reg_map[i]=Array.new(regs)}
313 (0..(steps-1)).each do |step|
314 use_locations.each do |e|
315 e.pop if e[-1] && e[-1]<step
317 local_use_map = Array.new(regs)
318 reg_map[step] = reg_map[step-1].clone if step>0
319 #(0..(regs-1)).each {|i| reg_map[step][i] = reg_map[step-1][i]}
320 use_map[step].each do |entry|
321 # print 'DBG: step='+step.to_s+' entry='+entry.to_s
322 found = reg_map[step].find_index(entry)
325 reg_map[step][found] = entry
326 local_use_map[found] = 1
329 if t0=reg_map[step].find_index(nil)
330 # print ' (found unsused slot)'
331 reg_map[step][t0] = entry
332 local_use_map[t0] = 1
334 # find a register to clear
335 a = reg_map[step].collect {|e| use_locations[e][-1]}
336 if t1 = a.find_index(nil)
337 # print ' (found not further used slot)'
338 reg_map[step][t1] = entry
340 # print ' (reassigned slot)'
341 reg_map[step][a.find_max_index] = entry
347 # puts 'DBG: map part ('+step.to_s+'): '+reg_map[step].inspect
349 return loads, reg_map
352 ################################################################################
356 ((j+1)..4).each do |k|
357 set_stat(f0_def[i][j], f0_def[i][k], i)
366 $stat.each_pair do |key,value|
367 if value[0]+value[3]>1 || value[1]+value[2]>1
368 # puts key+": \t"+value.inspect+": \t"+$stat_location[key]
369 dublets << [key, value, $stat_location[key]]
373 dublets.sort! do |x,y|
375 p = t[1].to_i - t[0].to_i
377 q = t[1].to_i - t[0].to_i
381 (x[2].split(',')[0].to_i-y[2].split(',')[0].to_i)
386 dublets.each {|e| e << idx; idx=(idx[0]+1).chr}
388 puts "useful combinations:"
389 dublets.each {|e| puts e[3]+': '+e[0]+' '*(5-e[0].length)+" \t"+e[1].inspect+" \t" +e[2]}
391 collisions = Array.new
392 puts "searching for collisions: "
393 (0..(dublets.length-2)).each do |i|
394 ((i+1)..(dublets.length-1)).each do |j|
395 if collision(dublets[i], dublets[j])
397 collisions << dublets[i][3]+dublets[j][3]
405 #puts collisions.join(',')
406 #puts "collision-map: "
407 #print_collision_map(collisions, dublets.length)
409 collision_lut = Array.new(dublets.length, 0)
410 (0..(dublets.length-1)).each do |x|
411 (0..(dublets.length-1)).each do |y|
412 if collisions.find_index(('A'[0]+x).chr+('A'[0]+y).chr) or
413 collisions.find_index(('A'[0]+y).chr+('A'[0]+x).chr)
414 collision_lut[x] |= 1<<y
420 puts "initializing bitcount table..."
423 puts "collision free combinations:"
425 combinations = [354997, 94005, 93877]
428 combinations = Array.new
430 percent_step =(2**dublets.length-1)/10000.0
431 next_step = (2**dublets.length-1)
433 (2**dublets.length-1).downto(0) do |x|
435 print "\x1b[s "+sprintf("%5.2f%%", percent/100.0)+"\x1b[u"
437 next_step -= percent_step
439 if check_collision(x, collision_lut) == false
441 combinations = Array.new if bits_set(x)>max
448 puts 'DBG: combinations: '+combinations.inspect
451 combinations.each do |c|
452 regs, reg_map = reg_map(word_to_steps(c, dublets), f0_def.length)
453 puts bits_set(c).to_s+': '+decode_word(c)+' ( '+(regs+1).to_s+' registers)'
454 print_reg_map(reg_map, regs+1, f0_def.length, 4)
456 steps = word_to_steps(combinations[-1], dublets)
457 regs, reg_map = reg_map(steps, f0_def.length)
459 generate_c_code(STDOUT, f0_def,steps, reg_map, use_map)
463 print q.collect {|v| v.to_s(16)}.join(', ')
466 reg_use_locations = Array.new(f0_def.length)
467 (0..(reg_use_locations.length-1)).each{|x| reg_use_locations[x] = Array.new}
469 (0..(f0_def.length-1)).each do |i|
470 use_map[i].each do |x|
471 reg_use_locations[x] << i
475 reg_use_locations.each{|x| x.reverse!}
476 #puts 'DBG: '+reg_use_locations.inspect
477 #puts 'DBG: (16 regs) '+calculate_load_pressure(use_map, reg_use_locations, 16, 16).inspect
478 #puts 'DBG: ( 8 regs) '+calculate_load_pressure(use_map, reg_use_locations, 8, 16).inspect
479 (4..16).each do |regs|
480 p,m = calculate_load_pressure(use_map, reg_use_locations, regs, 16)
481 puts "=#{regs} registers="
482 puts " load pressure: " +p.to_s
484 print_reg_map(m, regs, 16, 4)
485 # puts "DBG: reg_map: "+m.inspect
486 # puts "DBG: use_map: "+use_map.inspect