bmw/autogen_f0_asmmix.rb

   1 # autogen_f0_asm.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   tmp = +t[ 5] +t[10] +t[13] +(tr1=-t[ 7]+t[14]) ;
  21   q[ 0] = S32_0(tmp) + h[ 1];
  22   tmp = +t[ 8] +t[13] +t[ 0] -(tr2=+t[ 1]+t[10]) ;
  23   q[ 3] = S32_3(tmp) + h[ 4];
  24   tmp = -t[11] +t[13] -t[ 0] -t[ 3] +t[ 4] ;
  25   q[ 6] = S32_1(tmp) + h[ 7];
  26   tmp = +t[ 0] +(tr0=-t[ 3]+t[ 6]) +(tr1) ;
  27   q[ 9] = S32_4(tmp) + h[10];
  28   tmp = -t[ 9] -(tr0) +(tr2) ;
  29   q[12] = S32_2(tmp) + h[13];
  30   tmp = -t[ 4] +(tr0=-t[ 9]+t[12]) +(tr1=-t[ 6]+t[13]) ;
  31   q[15] = S32_0(tmp) + h[ 0];
  32   tmp = +t[ 7] +t[15] +t[ 0] -(tr0) ;
  33   q[ 2] = S32_2(tmp) + h[ 3];
  34   tmp = +t[10] +(tr0=-t[ 2]+t[15]) +(tr2=+t[ 3]-t[12]) ;
  35   q[ 5] = S32_0(tmp) + h[ 6];
  36   tmp = -t[ 5] -(tr0) +(tr1) ;
  37   q[ 8] = S32_3(tmp) + h[ 9];
  38   tmp = -t[ 0] -t[ 2] +t[ 9] +(tr0=-t[ 5]+t[ 8]) ;
  39   q[11] = S32_1(tmp) + h[12];
  40   tmp = -t[11] +(tr0) +(tr2) ;
  41   q[14] = S32_4(tmp) + h[15];
  42   tmp = +t[ 6] +(tr0=+t[11]+t[14]) -(tr1=+t[ 8]+t[15]) ;
  43   q[ 1] = S32_1(tmp) + h[ 2];
  44   tmp = +t[ 9] +t[ 1] +t[ 2] -(tr0) ;
  45   q[ 4] = S32_4(tmp) + h[ 5];
  46   tmp = -t[12] -t[14] +t[ 1] -t[ 4] -t[ 5] ;
  47   q[ 7] = S32_2(tmp) + h[ 8];
  48   tmp = -t[ 1] -(tr0=+t[ 4]+t[ 7]) +(tr1) ;
  49   q[10] = S32_0(tmp) + h[11];
  50   tmp = +t[ 2] +t[10] +t[11] +(tr0) ;
  51   q[13] = S32_3(tmp) + h[14];
  52 =end
  53 $c_code = <<EOF
  54   tmp = +t[ 5] +t[10] +t[13] +(tr1=-t[ 7]+t[14]) ;
  55   q[ 0] = S32_0(tmp) + h[ 1];
  56   tmp = +t[ 8] +t[13] +t[ 0] -(tr2=+t[ 1]+t[10]) ;
  57   q[ 3] = S32_3(tmp) + h[ 4];
  58   tmp = -t[11] +t[13] -t[ 0] -t[ 3] +t[ 4] ;
  59   q[ 6] = S32_1(tmp) + h[ 7];
  60   tmp = +t[ 0] +(tr0=-t[ 3]+t[ 6]) +(tr1) ;
  61   q[ 9] = S32_4(tmp) + h[10];
  62   tmp = -t[ 9] -(tr0) +(tr2) ;
  63   q[12] = S32_2(tmp) + h[13];
  64   tmp = -t[ 4] +(tr0=-t[ 9]+t[12]) +(tr1=-t[ 6]+t[13]) ;
  65   q[15] = S32_0(tmp) + h[ 0];
  66   tmp = +t[ 7] +t[15] +t[ 0] -(tr0) ;
  67   q[ 2] = S32_2(tmp) + h[ 3];
  68   tmp = +t[10] +(tr0=-t[ 2]+t[15]) +(tr2=+t[ 3]-t[12]) ;
  69   q[ 5] = S32_0(tmp) + h[ 6];
  70   tmp = -t[ 5] -(tr0) +(tr1) ;
  71   q[ 8] = S32_3(tmp) + h[ 9];
  72   tmp = -t[ 0] -t[ 2] +t[ 9] +(tr0=-t[ 5]+t[ 8]) ;
  73   q[11] = S32_1(tmp) + h[12];
  74   tmp = -t[11] +(tr0) +(tr2) ;
  75   q[14] = S32_4(tmp) + h[15];
  76   tmp = +t[ 6] +(tr0=+t[11]+t[14]) -(tr1=+t[ 8]+t[15]) ;
  77   q[ 1] = S32_1(tmp) + h[ 2];
  78   tmp = +t[ 9] +t[ 1] +t[ 2] -(tr0) ;
  79   q[ 4] = S32_4(tmp) + h[ 5];
  80   tmp = -t[12] -t[14] +t[ 1] -t[ 4] -t[ 5] ;
  81   q[ 7] = S32_2(tmp) + h[ 8];
  82   tmp = -t[ 1] -(tr0=+t[ 4]+t[ 7]) +(tr1) ;
  83   q[10] = S32_0(tmp) + h[11];
  84   tmp = +t[ 2] +t[10] +t[11] +(tr0) ;
  85   q[13] = S32_3(tmp) + h[14];
  86 EOF
  87
  88 $registers = ["r3", "r4", "r5", "r6", "r7", "r8", "r9", "r10", "r11", "r12", "r14"].reverse
  89
  90 class Array
  91   def chopf(n=1)
  92     return self[n..-1]
  93   end
  94 end
  95
  96 class String
  97   def chopf(n=1)
  98     return self[n..-1]
  99   end
 100
 101   def is_numeric?(b=10)
 102     n=self.to_i(b)
 103     s=n.to_s(b)
 104     (self==s) or (self==('+'+s))
 105   end
 106
 107   def xtr
 108     return self.to_i if self.is_numeric?
 109     self
 110   end
 111 end
 112
 113
 114 class Operation
 115   attr_reader :read_t
 116   attr_reader :read_tr
 117   attr_reader :write_tr0, :write_tr1, :write_tr2
 118   attr_reader :index, :s, :h
 119
 120   def init
 121     @read_t = Array.new
 122     @read_tr = Array.new
 123     @write_tr0 = Array.new
 124     @write_tr1 = Array.new
 125     @write_tr2 = Array.new
 126     @index = -1
 127     @s = -1
 128     @h = -1
 129   end
 130
 131   def parse(line)
 132     s = line
 133     while m = /([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 134       @read_t << m[1]+m[2]
 135       s = m[3]
 136     end
 137     s = line
 138     while m = /([+-])\(tr([012])(.*)/.match(s)
 139       @read_tr << m[1]+m[2]
 140       s = m[3]
 141     end
 142     s = line
 143     while m = /tr0=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 144       @write_tr0 << m[1]+m[2]
 145       @write_tr0 << m[3]+m[4]
 146       s = m[5]
 147     end
 148     s = line
 149     while m = /tr1=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 150       @write_tr1 << m[1]+m[2]
 151       @write_tr1 << m[3]+m[4]
 152       s = m[5]
 153     end
 154     s = line
 155     while m = /tr2=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 156       @write_tr2 << m[1]+m[2]
 157       @write_tr2 << m[3]+m[4]
 158       s = m[5]
 159     end
 160     if m=/q\[[\s]*([\d]*)\]/m.match(line)
 161       @index = m[1].to_i
 162     end
 163     if m=/S32_([0-4])\(tmp\)/m.match(line)
 164       @s = m[1].to_i
 165     end
 166     if m=/h\[[\s]*([\d]*)\]/m.match(line)
 167       @h = m[1].to_i
 168     end
 169   end
 170
 171 end
 172
 173
 174 $operations = Array.new
 175
 176 def parse_c_code
 177   i=0
 178   s = ''
 179   $c_code.each_line do |line|
 180 #    puts "DBG: line=", line
 181     if /^[\s]*tmp/.match(line)
 182       s = line
 183     end
 184     if /^[\s]*q\[[\s\d\]]/.match(line)
 185       s += line
 186       $operations[i] = Operation.new
 187       $operations[i].init
 188       $operations[i].parse(s)
 189       i+=1
 190     end
 191   end
 192 end
 193
 194 class Array
 195   def getsmallest(i=0)
 196     tmp = self.sort
 197     tmp.each {|x| return x if x>i}
 198     return nil
 199   end
 200
 201   def getlargestindex
 202     return self.index(nil) if self.index(nil)
 203     tmp = self.sort
 204     return self.index(tmp[-1])
 205   end
 206 end
 207
 208 def find_register_to_free(registermap, regusemap, step)
 209   if i=registermap.index(nil)
 210     return i
 211   end
 212   tmp = Array.new
 213   registermap.each do |x|
 214     if x.class==Fixnum and regusemap[x.abs]
 215       t = regusemap[x.abs].getsmallest(step)
 216       tmp << t
 217     else
 218       tmp << -1
 219     end
 220   end
 221   return tmp.getlargestindex
 222 end
 223
 224
 225 def load_registers(regmap, stack, op, step)
 226   asm_out = ''
 227   to_load2 = Array.new
 228   push_list = Array.new
 229   # set to_load2 to all registers which are not already loaded
 230 #  puts "DBG(a): "+regmap.inspect
 231   op.read_t.each do |x|
 232     x = x.to_i.abs
 233     to_load2 << x if regmap.index(x)==nil
 234   end
 235   to_load2.each do
 236     regmap[find_register_to_free(regmap, $regusemap, step)] = 'x'
 237   end
 238   if op.write_tr0.length!=0
 239     regmap[find_register_to_free(regmap, $regusemap, step)] = 'tr0'
 240   end
 241   if op.write_tr1.length!=0
 242     regmap[find_register_to_free(regmap, $regusemap, step)] = 'tr1'
 243   end
 244   if op.write_tr2.length!=0
 245     regmap[find_register_to_free(regmap, $regusemap, step)] = 'tr2'
 246   end
 247   to_load2.sort!
 248 =begin
 249   to_load2.length.times do |i|
 250     x = to_load2[i]
 251     y = to_load2[i+1]
 252     if x and y and (to_load2[i]+1 == to_load2[i+1]) and stack.index(x) and stack.index(y)
 253       rx = regmap.index('x')
 254       regmap[rx]=x.to_s
 255       ry = regmap.index('x')
 256       regmap[ry]=y.to_s
 257       asm_out += sprintf("  ldrd %s, %s, [SP, #%d*4]\n", $registers[rx], $registers[ry], x)
 258       to_load2[i] = nil
 259       to_load2[i+1] = nil
 260     end
 261   end
 262 =end
 263   to_load2.delete(nil)
 264   to_load2.each do |x|
 265     next if not x
 266     y = regmap.index('x')
 267     puts "Strange error!\n" if not y
 268     regmap[y]=x
 269     if stack.index(x)
 270       asm_out += sprintf("  ldr %s, [SP, #%d*4]\n", $registers[y], x)
 271     else
 272       asm_out += sprintf("  ldr %s, [r1, #%d*4]\n", $registers[y], x)
 273       asm_out += sprintf("  ldr %s, [r2, #%d*4]\n", $registers[-1], x)
 274       asm_out += sprintf("  eor %s, %s\n", $registers[y], $registers[-1])
 275       asm_out += sprintf("  str %s, [SP, #%d*4]\n", $registers[y], x)
 276       stack << x
 277 #      push_list << [$registers[y], x]
 278     end
 279   end
 280 #  if push_list.length!=0
 281 #    push_list.sort!{ |x,y| x[0].chopf.to_i <=> y[0].chopf.to_i}
 282 #    push_regs = push_list.collect {|x| x[0]}
 283 #    push_list.reverse.each {|x| stack << x[1]}
 284 #    asm_out += sprintf("  stmdb SP, {%s}\n", push_regs.join(', '))
 285 #  end
 286 #  puts asm_out
 287 #  puts "DBG(0): "+regmap.inspect
 288 #  puts "DBG(1): "+to_load.inspect
 289 #  puts "DBG(2): "+to_load2.inspect
 290
 291   #puts 'DBG('+__LINE__.to_s+'): regmap = '+regmap.inspect
 292   return regmap, stack, asm_out
 293 end
 294
 295 def gen_simple_assembler(operations)
 296   asm_out=''
 297   stack = Array.new
 298   accu = $registers.length-1
 299 #  outr = $registers.length-4
 300 #  tr0 =  $registers.length-3
 301 #  tr1 =  $registers.length-2
 302 #  tr2 =  $registers.length-4
 303
 304   reg_cnt = $registers.length-1
 305   regmap = Array.new(reg_cnt)
 306   reg_idx=0
 307   step = 0
 308   asm_out += sprintf("  sub SP, #%d*4\n", 16)
 309   operations.each do |op|
 310     asm_out += sprintf("/*=== W[%2d] ===*/\n", op.index)
 311     regmap, stack, tstr = load_registers(regmap, stack, op, step-1)
 312     asm_out += tstr
 313     step += 1
 314     reg_hash = Hash.new
 315     op.read_t.each do |t|
 316       if regmap.index(t.chopf.to_i)==nil
 317         printf("ERROR: too few registers!\n")
 318       end
 319       reg_hash[t.chopf.to_i]=regmap.index(t.chopf.to_i)
 320     end
 321     if op.write_tr0.length==2
 322       signs_code=op.write_tr0[0][0..0]+op.write_tr0[1][0..0]
 323       case signs_code
 324         when "++"
 325           asm_out += sprintf("  add %s, %s, %s\n", $registers[regmap.index('tr0')], \
 326             $registers[reg_hash[op.write_tr0[0].chopf.to_i]], \
 327             $registers[reg_hash[op.write_tr0[1].chopf.to_i]])
 328         when "+-"
 329           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr0')], \
 330             $registers[reg_hash[op.write_tr0[0].chopf.to_i]], \
 331             $registers[reg_hash[op.write_tr0[1].chopf.to_i]])
 332         when "-+"
 333           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr0')], \
 334             $registers[reg_hash[op.write_tr0[1].chopf.to_i]], \
 335             $registers[reg_hash[op.write_tr0[0].chopf.to_i]])
 336         else
 337           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 338           puts op.inspect
 339       end
 340     end
 341     if op.write_tr1.length==2
 342       signs_code=op.write_tr1[0][0..0]+op.write_tr1[1][0..0]
 343       case signs_code
 344         when "++"
 345           asm_out += sprintf("  add %s, %s, %s\n", $registers[regmap.index('tr1')], \
 346             $registers[reg_hash[op.write_tr1[0].chopf.to_i]], \
 347             $registers[reg_hash[op.write_tr1[1].chopf.to_i]])
 348         when "+-"
 349           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr1')], \
 350             $registers[reg_hash[op.write_tr1[0].chopf.to_i]], \
 351             $registers[reg_hash[op.write_tr1[1].chopf.to_i]])
 352         when "-+"
 353   #        puts 'DBG: '+reg_hash.inspect
 354           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr1')], \
 355             $registers[reg_hash[op.write_tr1[1].chopf.to_i]], \
 356             $registers[reg_hash[op.write_tr1[0].chopf.to_i]])
 357         else
 358           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 359           puts op.inspect
 360       end
 361     end
 362     if op.write_tr2.length==2
 363       signs_code=op.write_tr2[0][0..0]+op.write_tr2[1][0..0]
 364       case signs_code
 365         when "++"
 366           asm_out += sprintf("  add %s, %s, %s\n", $registers[regmap.index('tr2')], \
 367             $registers[reg_hash[op.write_tr2[0].chopf.to_i]], \
 368             $registers[reg_hash[op.write_tr2[1].chopf.to_i]])
 369         when "+-"
 370           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr2')], \
 371             $registers[reg_hash[op.write_tr2[0].chopf.to_i]], \
 372             $registers[reg_hash[op.write_tr2[1].chopf.to_i]])
 373         when "-+"
 374           asm_out += sprintf("  sub %s, %s, %s\n", $registers[regmap.index('tr2')], \
 375             $registers[reg_hash[op.write_tr2[1].chopf.to_i]], \
 376             $registers[reg_hash[op.write_tr2[0].chopf.to_i]])
 377         else
 378           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 379           puts op.inspect
 380       end
 381     end
 382     reg_hash['0tr'] = regmap.index('tr0')
 383     reg_hash['1tr'] = regmap.index('tr1')
 384     reg_hash['2tr'] = regmap.index('tr2')
 385     tr_to_delete = op.read_tr.collect { |x| x.chopf}
 386     tr_to_delete.delete('0') if op.write_tr0.length!=0
 387     tr_to_delete.delete('1') if op.write_tr1.length!=0
 388     tr_to_delete.delete('2') if op.write_tr2.length!=0
 389     tr_to_delete.each do |x|
 390       y = regmap.index('tr'+x)
 391       regmap[y]=nil if y
 392  #     puts 'DBG('+__LINE__.to_s+') deleted tr'+x+' @ '+y.to_s
 393     end
 394     operations_to_do = op.read_t
 395     op.read_tr.each {|x| operations_to_do << x+'tr'}
 396     op.write_tr0.each {|x| operations_to_do.delete(x)}
 397     op.write_tr1.each {|x| operations_to_do.delete(x)}
 398     op.write_tr2.each {|x| operations_to_do.delete(x)}
 399     operations_to_do = operations_to_do.sort
 400     asm_out += sprintf("/*(-- should do %s --)*/\n", operations_to_do.join(', '));
 401     sign_code=operations_to_do[1][0..0]
 402     case sign_code
 403       when '+'
 404    #     puts 'DBG('+__LINE__.to_s+'): x='+operations_to_do[0]+' reg_hash='+reg_hash.inspect
 405         asm_out += sprintf("  add %s, %s, %s\n", $registers[accu], \
 406           $registers[reg_hash[operations_to_do[0].chopf.xtr]], \
 407           $registers[reg_hash[operations_to_do[1].chopf.xtr]])
 408       when '-'
 409     #    puts 'DBG('+__LINE__.to_s+'): x='+x+' reg_hash='+reg_hash.inspect
 410         asm_out += sprintf("  sub %s, %s, %s\n", $registers[accu], \
 411           $registers[reg_hash[operations_to_do[0].chopf.xtr]], \
 412           $registers[reg_hash[operations_to_do[1].chopf.xtr]])
 413     end
 414     operations_to_do = operations_to_do[2..-1]
 415     operations_to_do.each do |x|
 416       sign_code=x[0..0]
 417       case sign_code
 418         when '+'
 419  #         puts 'DBG('+__LINE__.to_s+'): x='+x+' reg_hash='+reg_hash.inspect
 420           asm_out += sprintf("  add %s, %s\n", $registers[accu], \
 421             $registers[reg_hash[x.chopf.xtr]])
 422         when '-'
 423           asm_out += sprintf("  sub %s, %s\n", $registers[accu], \
 424             $registers[reg_hash[x.chopf.xtr]])
 425       end
 426     end
 427     outr = find_register_to_free(regmap, $regusemap, step)
 428     regmap[outr]=nil
 429     if(op.s==4)
 430       asm_out += sprintf("  S32_4 %s\n", $registers[accu])
 431       asm_out += sprintf("  ldr %s, [r1, #%d*4]\n", $registers[outr], op.h)
 432       asm_out += sprintf("  add %s, %s\n", $registers[accu], $registers[outr])
 433       asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[accu], op.index)
 434     else
 435       asm_out += sprintf("  S32_%d %s %s\n", op.s, $registers[outr], $registers[accu])
 436       asm_out += sprintf("  ldr %s, [r1, #%d*4]\n", $registers[accu], op.h)
 437       asm_out += sprintf("  add %s, %s\n", $registers[outr], $registers[accu])
 438       asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[outr], op.index)
 439     end
 440
 441 #  asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[accu], op.index)
 442   end
 443   asm_out += sprintf("  add SP, #%d*4", 16)
 444   return asm_out
 445 end
 446
 447 class RegMapEntry
 448   attr_accessor :usemap
 449   attr_accessor :nextusemap
 450 end
 451 =begin
 452 class RegMap
 453   atrr_reader :steps
 454   atrr_reader :entrys
 455   attr_reader :regcnt
 456 end
 457
 458 def gen_regmap_simple
 459
 460 end
 461 =end
 462 $regusemap = Array.new
 463
 464 def build_regusemap(operations)
 465   i=0
 466   operations.each do |op|
 467     op.read_t.each do |t|
 468       x = t.chopf.to_i
 469       if $regusemap[x]==nil
 470         $regusemap[x]=Array.new
 471       end
 472       $regusemap[x]<<i
 473     end
 474     i += 1
 475   end
 476 end
 477
 478 #-------------------------------------------------------------------------------
 479 # MAIN
 480 #-------------------------------------------------------------------------------
 481
 482 parse_c_code
 483 #puts $operations.inspect
 484 build_regusemap($operations)
 485 #puts $regusemap.inspect
 486 puts gen_simple_assembler($operations)
 487