]> git.cryptolib.org Git - arm-crypto-lib.git/blob - bmw/analyze_f0.rb
adding install_headers.sh script
[arm-crypto-lib.git] / bmw / analyze_f0.rb
1 # analyze_f0.rb 
2 =begin
3     This file is part of the ARM-Crypto-Lib.
4     Copyright (C) 2006-2010  Daniel Otte (daniel.otte@rub.de)
5
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.
10
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.
15
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/>.
18 =end
19 =begin
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]);
36 =end
37 f0_def = 
38 [
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']
55 ]
56   
57 $stat=Hash.new
58 $stat_location=Hash.new
59
60 def set_stat(s1,s2,i)
61   if s2.to_i.abs<s1.to_i.abs
62     t = s1
63     s1 = s2
64     s2 = t
65   end
66   idx = nil
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()
75   else
76     $stat_location[(s1[1..-1]+','+s2[1..-1])] += ','+i.to_s() 
77   end
78   $stat[(s1[1..-1]+','+s2[1..-1])][idx]+= 1
79 end
80
81 def collision(x,y)
82   r=0
83   va = x[0].split(',')
84   vb = y[0].split(',')
85   va.each do |p|
86     r=1 if vb.find_index(p)
87   end
88   return false if r==0
89   va = x[2].split(',')
90   vb = y[2].split(',')
91   va.each do |p|
92     r=2 if vb.find_index(p)
93   end
94   return false if r==1
95   return true
96 end
97
98 def reg_empty(map, reg, from, to)
99   (from..to).each do |x|
100     return false if(map[x][reg])
101   end
102   return true
103 end
104
105 def reg_set(map, reg, from, to, value)
106    (from..to).each do |x|
107     map[x][reg] = value
108   end
109   
110 end
111
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))
116     print ':'
117     (0..(length-1)).each do |x|
118       if map[x][r]==nil
119         print ' '
120       else 
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
123       end
124     end
125     print "\n"
126   end
127 end
128
129 def reg_map(steps, length)
130   max_reg=0
131   map = Array.new(length)
132   (0..(length-1)).each {|x| map[x]=Array.new}
133   steps.each do |step|
134     reg=0
135     a = step[2].split(',').collect { |x| x.to_i}
136     a.sort!
137     from = a[0]
138     to = a[-1]
139     while(reg_empty(map,reg,from,to)==false)
140       reg += 1
141     end
142     reg_set(map, reg, from, to, step[3])
143     max_reg=reg if reg>max_reg
144   end
145   return max_reg, map
146 end
147
148 def word_to_steps(word, list)
149   steps=Array.new
150   idx=0
151   while(word!=0)
152     if(word&1==1)
153       steps << list[idx]
154     end
155     word >>= 1
156     idx += 1
157   end
158   return steps
159 end
160
161 def print_collision_map(collisions, length)
162   print '  '
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))
169         print('x ')
170       else
171         print('  ')
172       end
173     end 
174   end 
175   print("\n")
176 end
177
178 def check_collision(word, lut)
179   (0..(lut.length-1)).each do |i|
180     if word&(1<<i)!=0
181       return true if word&lut[i]!=0
182     end
183   end
184   return false
185 end
186
187 $bitcount_lut = Array.new(65536)
188
189 def bits_set_simple(x)
190   r = 0
191   while(x!=0)
192     r+=1 if(x&1==1)
193     x >>=1
194   end
195   return r
196 end
197
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)}
202 end
203
204 def bits_set(x, length=16)
205   r=0
206   while(x!=0)
207     r += $bitcount_lut[x&(2**length-1)]
208     x >>= length
209   end
210   return r
211 end
212
213 def decode_word(word)
214   idx='A'
215   r = ''
216   while(word!=0)
217     if(word&1==1)
218       r += idx
219     end
220     word >>= 1
221     idx = (idx[0]+1).chr
222   end
223   return r
224 end
225
226 def generate_c_code(fout, func, optimizations=[], reg_map=[], use_map=[])
227   out_interval = 3
228   out_modulus = 16
229   out_idx = 0
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)
241       set = false
242       free = false
243       if step==opt_steps[0]
244         sign_out='+'
245         set=true
246       else
247         i=0
248         while opt_table[opt_steps[0]][i][4]!=reg_a || opt_table[opt_steps[0]][i][5]!=reg_b
249           i+=1
250         end
251         if(sign_a==opt_table[opt_steps[0]][i][0])
252           sign_out='+'
253         else
254           sign_out='-'
255         end
256       end
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]
262     end
263   end
264   (0..(func.length-1)).each do |i|
265     fout.printf("q[%2d] = ", out_idx)
266     out_idx = (out_idx+out_interval)%out_modulus
267     use_map << Array.new
268     func[i].each do |j|
269       skip = 0
270       if opt_table[i]
271         opt_table[i].each do |opt|
272           skip = 1 if opt[4]==j[1..-1] or opt[5]==j[1..-1]
273         end
274       end
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
277     end
278     if opt_table[i]
279       opt_table[i].each do |opt|
280         fout.print(opt[2]+'('+opt[3])
281         if opt[6]
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
285         end
286         fout.print(') ')
287       end
288     end  
289     fout.print(";\n")
290   end
291 end
292
293 class Array
294   def find_max_index
295     return nil if self.length==0
296     maxidx=0
297     max=self[0]
298     self.each do |i|
299       if(self[i]!=nil && max<self[i])
300         maxidx = i
301         max = self[i]
302       end
303     end
304     return maxidx
305   end
306
307 end
308
309 def calculate_load_pressure(use_map, use_locations, regs, steps)
310   loads=0
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
316     end
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)
323       if found!=nil
324 #        print ' (direct)'
325         reg_map[step][found] = entry
326         local_use_map[found] = 1
327       else 
328         loads += 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
333         else
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
339           else
340 #            print ' (reassigned slot)'
341             reg_map[step][a.find_max_index] = entry
342           end
343         end
344       end
345 #      print "\n"
346     end
347 #    puts 'DBG: map part ('+step.to_s+'): '+reg_map[step].inspect
348   end
349   return loads, reg_map
350 end
351
352 ################################################################################
353
354 (0..15).each do |i|
355   (0..3). each do |j|
356     ((j+1)..4).each do |k|
357       set_stat(f0_def[i][j], f0_def[i][k], i)
358     end
359   end
360 end
361
362
363
364 dublets = Array.new
365
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]]
370   end
371 end
372
373 dublets.sort! do |x,y| 
374   t = x[2].split(',')
375   p = t[1].to_i - t[0].to_i 
376   t = y[2].split(',')
377   q = t[1].to_i - t[0].to_i
378   if (p!=q)
379     (p-q)
380   else
381     (x[2].split(',')[0].to_i-y[2].split(',')[0].to_i)
382   end  
383 end
384
385 idx='A'
386 dublets.each {|e| e << idx; idx=(idx[0]+1).chr}
387
388 puts "useful combinations:"
389 dublets.each {|e| puts e[3]+': '+e[0]+' '*(5-e[0].length)+" \t"+e[1].inspect+" \t" +e[2]}
390
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])
396       print '*'
397       collisions << dublets[i][3]+dublets[j][3]
398     else
399       print '.'
400     end
401   end
402 end
403 puts ''
404 #puts "collisions: "
405 #puts collisions.join(',')
406 #puts "collision-map: "
407 #print_collision_map(collisions, dublets.length)
408
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
415     end   
416   end 
417 end
418
419
420 puts "initializing bitcount table..."
421 init_bitcount_lut
422
423 puts "collision free combinations:"
424 puts "(from cache)"
425 combinations = [354997, 94005, 93877]
426 if combinations==nil
427   max = 0
428   combinations = Array.new
429   percent = 0
430   percent_step =(2**dublets.length-1)/10000.0
431   next_step = (2**dublets.length-1)
432   puts ''
433   (2**dublets.length-1).downto(0) do |x|
434     if(x<=next_step)
435       print "\x1b[s "+sprintf("%5.2f%%", percent/100.0)+"\x1b[u"
436       percent += 1
437       next_step -= percent_step
438     end
439     if check_collision(x, collision_lut) == false
440       if bits_set(x)>= max
441         combinations = Array.new if bits_set(x)>max
442         combinations << x
443         max = bits_set(x)
444       end
445     end
446   end
447   
448   puts 'DBG: combinations: '+combinations.inspect
449 end
450
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)
455 end
456 steps = word_to_steps(combinations[-1], dublets)
457 regs, reg_map = reg_map(steps, f0_def.length)
458 use_map = []
459 generate_c_code(STDOUT, f0_def,steps, reg_map, use_map)
460 puts 'DBG: '
461 use_map.each do |q|
462   print "\t[ "
463   print q.collect {|v| v.to_s(16)}.join(', ')
464   print " ]\n"
465 end
466 reg_use_locations = Array.new(f0_def.length)
467 (0..(reg_use_locations.length-1)).each{|x| reg_use_locations[x] = Array.new}
468
469 (0..(f0_def.length-1)).each do |i|
470   use_map[i].each do |x|
471     reg_use_locations[x]  << i
472   end
473 end
474
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
483   puts "  map: "
484   print_reg_map(m, regs, 16, 4)
485 #  puts "DBG: reg_map: "+m.inspect
486 #  puts "DBG: use_map: "+use_map.inspect
487 end