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