bmw/autogen_f0_asm.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 = ["r2", "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 end
 101
 102
 103 class Operation
 104   attr_reader :read_t
 105   attr_reader :read_tr
 106   attr_reader :write_tr0, :write_tr1, :write_tr2
 107   attr_reader :index, :s, :h
 108
 109   def init
 110     @read_t = Array.new
 111     @read_tr = Array.new
 112     @write_tr0 = Array.new
 113     @write_tr1 = Array.new
 114     @write_tr2 = Array.new
 115     @index = -1
 116     @s = -1
 117     @h = -1
 118   end
 119
 120   def parse(line)
 121     s = line
 122     while m = /([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 123       @read_t << m[1]+m[2]
 124       s = m[3]
 125     end
 126     s = line
 127     while m = /([+-])\(tr([012])(.*)/.match(s)
 128       @read_tr << m[1]+m[2]
 129       s = m[3]
 130     end
 131     s = line
 132     while m = /tr0=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 133       @write_tr0 << m[1]+m[2]
 134       @write_tr0 << m[3]+m[4]
 135       s = m[5]
 136     end
 137     s = line
 138     while m = /tr1=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 139       @write_tr1 << m[1]+m[2]
 140       @write_tr1 << m[3]+m[4]
 141       s = m[5]
 142     end
 143     s = line
 144     while m = /tr2=([+-])t\[[\s]*([\d]*)\][\s]*([+-])t\[[\s]*([\d]*)\](.*)/.match(s)
 145       @write_tr2 << m[1]+m[2]
 146       @write_tr2 << m[3]+m[4]
 147       s = m[5]
 148     end
 149     if m=/q\[[\s]*([\d]*)\]/m.match(line)
 150       @index = m[1].to_i
 151     end
 152     if m=/S32_([0-4])\(tmp\)/m.match(line)
 153       @s = m[1].to_i
 154     end
 155     if m=/h\[[\s]*([\d]*)\]/m.match(line)
 156       @h = m[1].to_i
 157     end
 158   end
 159
 160 end
 161
 162
 163 $operations = Array.new
 164
 165 def parse_c_code
 166   i=0
 167   s = ''
 168   $c_code.each_line do |line|
 169 #    puts "DBG: line=", line
 170     if /^[\s]*tmp/.match(line)
 171       s = line
 172     end
 173     if /^[\s]*q\[[\s\d\]]/.match(line)
 174       s += line
 175       $operations[i] = Operation.new
 176       $operations[i].init
 177       $operations[i].parse(s)
 178       i+=1
 179     end
 180   end
 181 end
 182
 183 class Array
 184   def getsmallest(i=0)
 185     tmp = self.sort
 186     tmp.each {|x| return x if x>i}
 187     return nil
 188   end
 189
 190   def getlargestindex
 191     return self.index(nil) if self.index(nil)
 192     tmp = self.sort
 193     return self.index(tmp[-1])
 194   end
 195 end
 196
 197 def find_register_to_free(registermap, regusemap, step)
 198   if i=registermap.index(nil)
 199     return i
 200   end
 201   tmp = Array.new
 202   registermap.each do |x|
 203     if x!='x' and regusemap[x.to_i.abs]
 204       t = regusemap[x.to_i.abs].getsmallest(step)
 205       tmp << t
 206     else
 207       tmp << -1
 208     end
 209   end
 210   return tmp.getlargestindex
 211 end
 212
 213 def unused_registers(regoccupation, operation)
 214   tmp = Array.new
 215   tmp2 = Array.new
 216   t = Array.new
 217   operation.read_t.each do |x|
 218     t << x.chopf
 219   end
 220   regoccupation.each do |x|
 221     tmp << x if t.index(x)==nil
 222   end
 223   regoccupation.each do |x|
 224     tmp2 << x if tmp.index(x)==nil
 225   end
 226
 227   return tmp,tmp2
 228 end
 229
 230 def load_registers(regmap, to_load, step)
 231   asm_out = ''
 232   to_load2 = Array.new
 233   # set to_load2 to all registers which are not already loaded
 234 #  puts "DBG(a): "+regmap.inspect
 235   to_load.each do |x|
 236     x = x.to_i.abs
 237     to_load2 << x if regmap.index(x)==nil
 238   end
 239   to_load2.each do
 240     regmap[find_register_to_free(regmap, $regusemap, step)] = 'x'
 241   end
 242   to_load2.sort!
 243 =begin
 244   to_load2.length.times do |i|
 245     if to_load2[i] and (to_load2[i]+1 == to_load2[i+1])
 246       t1 = regmap.index('x')
 247       regmap[t1] = to_load2[i].to_s
 248       t2 = regmap.index('x')
 249       regmap[t2] = to_load2[i+1].to_s
 250       asm_out += sprintf("  ldrd %s, %s, T%02d_ADDR\n", $registers[t1], $registers[t2], to_load2[i+1])
 251 #     asm_out += sprintf("  ldr %s, T%02d_ADDR\n", $registers[t1], x)
 252 #      asm_out += sprintf("  ldr %s, T%02d_ADDR\n", $registers[t2], x)
 253       to_load2[i] = nil
 254
 255       to_load2[i+1] = nil
 256     end
 257   end
 258 =end
 259   to_load2.delete(nil)
 260   to_load2.each do |x|
 261     y = regmap.index('x')
 262     puts "Strange error!\n" if not y
 263     regmap[y]=x.to_s
 264     asm_out += sprintf("  ldr %s, T%02d_ADDR\n", $registers[y], x)
 265   end
 266 #  puts asm_out
 267 #  puts "DBG(0): "+regmap.inspect
 268 #  puts "DBG(1): "+to_load.inspect
 269 #  puts "DBG(2): "+to_load2.inspect
 270   return regmap, asm_out
 271 end
 272
 273 def gen_simple_assembler(operations)
 274   asm_out=''
 275   accu = $registers.length-4
 276 #  outr = $registers.length-4
 277   tr0 =  $registers.length-3
 278   tr1 =  $registers.length-2
 279   tr2 =  $registers.length-1
 280
 281   reg_cnt = $registers.length-4
 282   regmap = Array.new(reg_cnt)
 283   reg_idx=0
 284   step = 0
 285   operations.each do |op|
 286     asm_out += sprintf("/*=== W[%2d] ===*/\n", op.index)
 287     regmap, tstr = load_registers(regmap, op.read_t, step-1)
 288     asm_out += tstr
 289     step += 1
 290     reg_hash = Hash.new
 291     op.read_t.each do |t|
 292       if regmap.index(t.chopf)==nil
 293         printf("ERROR: too few registers!\n")
 294       end
 295       reg_hash[t.chopf]=regmap.index(t.chopf)
 296     end
 297     if op.write_tr0.length==2
 298       signs_code=op.write_tr0[0][0..0]+op.write_tr0[1][0..0]
 299       case signs_code
 300         when "++"
 301           asm_out += sprintf("  add %s, %s, %s\n", $registers[tr0], \
 302             $registers[reg_hash[op.write_tr0[0].chopf]], \
 303             $registers[reg_hash[op.write_tr0[1].chopf]])
 304         when "+-"
 305           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr0], \
 306             $registers[reg_hash[op.write_tr0[0].chopf]], \
 307             $registers[reg_hash[op.write_tr0[1].chopf]])
 308         when "-+"
 309           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr0], \
 310             $registers[reg_hash[op.write_tr0[1].chopf]], \
 311             $registers[reg_hash[op.write_tr0[0].chopf]])
 312         else
 313           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 314           puts op.inspect
 315       end
 316     end
 317     if op.write_tr1.length==2
 318       signs_code=op.write_tr1[0][0..0]+op.write_tr1[1][0..0]
 319       case signs_code
 320         when "++"
 321           asm_out += sprintf("  add %s, %s, %s\n", $registers[tr1], \
 322             $registers[reg_hash[op.write_tr1[0].chopf]], \
 323             $registers[reg_hash[op.write_tr1[1].chopf]])
 324         when "+-"
 325           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr1], \
 326             $registers[reg_hash[op.write_tr1[0].chopf]], \
 327             $registers[reg_hash[op.write_tr1[1].chopf]])
 328         when "-+"
 329           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr1], \
 330             $registers[reg_hash[op.write_tr1[1].chopf]], \
 331             $registers[reg_hash[op.write_tr1[0].chopf]])
 332         else
 333           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 334           puts op.inspect
 335       end
 336     end
 337     if op.write_tr2.length==2
 338       signs_code=op.write_tr2[0][0..0]+op.write_tr2[1][0..0]
 339       case signs_code
 340         when "++"
 341           asm_out += sprintf("  add %s, %s, %s\n", $registers[tr2], \
 342             $registers[reg_hash[op.write_tr2[0].chopf]], \
 343             $registers[reg_hash[op.write_tr2[1].chopf]])
 344         when "+-"
 345           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr2], \
 346             $registers[reg_hash[op.write_tr2[0].chopf]], \
 347             $registers[reg_hash[op.write_tr2[1].chopf]])
 348         when "-+"
 349           asm_out += sprintf("  sub %s, %s, %s\n", $registers[tr2], \
 350             $registers[reg_hash[op.write_tr2[1].chopf]], \
 351             $registers[reg_hash[op.write_tr2[0].chopf]])
 352         else
 353           printf("ERROR: invalid signs_code (%d): %s\n", __LINE__, signs_code)
 354           puts op.inspect
 355       end
 356     end
 357     reg_hash['0tr'] = tr0
 358     reg_hash['1tr'] = tr1
 359     reg_hash['2tr'] = tr2
 360     operations_to_do = op.read_t
 361     op.read_tr.each {|x| operations_to_do << x+'tr'}
 362     op.write_tr0.each {|x| operations_to_do.delete(x)}
 363     op.write_tr1.each {|x| operations_to_do.delete(x)}
 364     op.write_tr2.each {|x| operations_to_do.delete(x)}
 365     operations_to_do = operations_to_do.sort
 366     asm_out += sprintf("/*(-- should do %s --)*/\n", operations_to_do.join(', '));
 367     sign_code=operations_to_do[1][0..0]
 368     case sign_code
 369       when '+'
 370         asm_out += sprintf("  add %s, %s, %s\n", $registers[accu], \
 371           $registers[reg_hash[operations_to_do[0].chopf]], \
 372           $registers[reg_hash[operations_to_do[1].chopf]])
 373       when '-'
 374         asm_out += sprintf("  sub %s, %s, %s\n", $registers[accu], \
 375           $registers[reg_hash[operations_to_do[0].chopf]], \
 376           $registers[reg_hash[operations_to_do[1].chopf]])
 377     end
 378     operations_to_do = operations_to_do[2..-1]
 379     operations_to_do.each do |x|
 380       sign_code=x[0..0]
 381       case sign_code
 382         when '+'
 383           asm_out += sprintf("  add %s, %s\n", $registers[accu], \
 384             $registers[reg_hash[x.chopf]])
 385         when '-'
 386           asm_out += sprintf("  sub %s, %s\n", $registers[accu], \
 387             $registers[reg_hash[x.chopf]])
 388       end
 389     end
 390     outr = find_register_to_free(regmap, $regusemap, step)
 391     regmap[outr]=nil
 392     if(op.s==4)
 393       asm_out += sprintf("  S32_4 %s\n", $registers[accu])
 394       asm_out += sprintf("  ldr %s, [r1, #%d*4]\n", $registers[outr], op.h)
 395       asm_out += sprintf("  add %s, %s\n", $registers[accu], $registers[outr])
 396       asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[accu], op.index)
 397     else
 398       asm_out += sprintf("  S32_%d %s %s\n", op.s, $registers[outr], $registers[accu])
 399       asm_out += sprintf("  ldr %s, [r1, #%d*4]\n", $registers[accu], op.h)
 400       asm_out += sprintf("  add %s, %s\n", $registers[outr], $registers[accu])
 401       asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[outr], op.index)
 402     end
 403
 404 #  asm_out += sprintf("  str %s, [r0, #%d*4]\n", $registers[accu], op.index)
 405   end
 406   return asm_out
 407 end
 408
 409 class RegMapEntry
 410   attr_accessor :usemap
 411   attr_accessor :nextusemap
 412 end
 413 =begin
 414 class RegMap
 415   atrr_reader :steps
 416   atrr_reader :entrys
 417   attr_reader :regcnt
 418 end
 419
 420 def gen_regmap_simple
 421
 422 end
 423 =end
 424 $regusemap = Array.new
 425
 426 def build_regusemap(operations)
 427   i=0
 428   operations.each do |op|
 429     op.read_t.each do |t|
 430       x = t.chopf.to_i
 431       if $regusemap[x]==nil
 432         $regusemap[x]=Array.new
 433       end
 434       $regusemap[x]<<i
 435     end
 436     i += 1
 437   end
 438 end
 439
 440 #-------------------------------------------------------------------------------
 441 # MAIN
 442 #-------------------------------------------------------------------------------
 443
 444 parse_c_code
 445 #puts $operations.inspect
 446 build_regusemap($operations)
 447 #puts $regusemap.inspect
 448 puts gen_simple_assembler($operations)
 449