301array-equal.subx

   1 # Comparing arrays of numbers.
   2
   3 == code
   4
   5 array-equal?:  # a: (addr array int), b: (addr array int) -> result/eax: boolean
   6     # pseudocode:
   7     #   asize = a->size
   8     #   if (asize != b->size) return false
   9     #   i = 0
  10     #   curra = a->data
  11     #   currb = b->data
  12     #   while i < asize
  13     #     i1 = *curra
  14     #     i2 = *currb
  15     #     if (c1 != c2) return false
  16     #     i+=4, curra+=4, currb+=4
  17     #   return true
  18     #
  19     # registers:
  20     #   i: ecx
  21     #   asize: edx
  22     #   curra: esi
  23     #   currb: edi
  24     #   i1: eax
  25     #   i2: ebx
  26     #
  27     # . prologue
  28     55/push-ebp
  29     89/<- %ebp 4/r32/esp
  30     # . save registers
  31     51/push-ecx
  32     52/push-edx
  33     53/push-ebx
  34     56/push-esi
  35     57/push-edi
  36     # esi = a
  37     8b/-> *(ebp+8) 6/r32/esi
  38     # edi = b
  39     8b/-> *(ebp+0xc) 7/r32/edi
  40     # var asize/edx: int = a->size
  41     8b/-> *esi 2/r32/edx
  42 $array-equal?:sizes:
  43     # if (asize != b->size) return false
  44     39/compare *edi 2/r32/edx
  45     75/jump-if-!= $array-equal?:false/disp8
  46     # var curra/esi: (addr byte) = a->data
  47     81 0/subop/add %esi 4/imm32
  48     # var currb/edi: (addr byte) = b->data
  49     81 0/subop/add %edi 4/imm32
  50     # var i/ecx: int = 0
  51     31/xor-with %ecx 1/r32/ecx
  52     # var vala/eax: int
  53     # var valb/ebx: int
  54 $array-equal?:loop:
  55     # if (i >= asize) return true
  56     39/compare %ecx 2/r32/edx
  57     7d/jump-if->= $array-equal?:true/disp8
  58     # var vala/eax: int = *curra
  59     8b/-> *esi 0/r32/eax
  60     # var valb/ebx: int = *currb
  61     8b/-> *edi 3/r32/ebx
  62     # if (vala != valb) return false
  63     39/compare %eax 3/r32/ebx
  64     75/jump-if-!= $array-equal?:false/disp8
  65     # i += 4
  66     81 0/subop/add %ecx 4/imm32
  67     # currs += 4
  68     81 0/subop/add %esi 4/imm32
  69     # currb += 4
  70     81 0/subop/add %edi 4/imm32
  71     eb/jump $array-equal?:loop/disp8
  72 $array-equal?:true:
  73     b8/copy-to-eax 1/imm32
  74     eb/jump $array-equal?:end/disp8
  75 $array-equal?:false:
  76     b8/copy-to-eax 0/imm32
  77 $array-equal?:end:
  78     # . restore registers
  79     5f/pop-to-edi
  80     5e/pop-to-esi
  81     5b/pop-to-ebx
  82     5a/pop-to-edx
  83     59/pop-to-ecx
  84     # . epilogue
  85     89/<- %esp 5/r32/ebp
  86     5d/pop-to-ebp
  87     c3/return
  88
  89 test-compare-empty-with-empty-array:
  90     # . prologue
  91     55/push-ebp
  92     89/<- %ebp 4/r32/esp
  93     # var ecx: (array _) = []
  94     68/push 0/imm32/size
  95     89/<- %ecx 4/r32/esp
  96     # var edx: (array _) = []
  97     68/push 0/imm32/size
  98     89/<- %edx 4/r32/esp
  99     #
 100     (array-equal? %ecx %edx)  # => eax
 101     (check-ints-equal %eax 1 "F - test-compare-empty-with-empty-array")
 102     # . epilogue
 103     89/<- %esp 5/r32/ebp
 104     5d/pop-to-ebp
 105     c3/return
 106
 107 test-compare-empty-with-non-empty-array:  # also checks size-mismatch code path
 108     # . prologue
 109     55/push-ebp
 110     89/<- %ebp 4/r32/esp
 111     # var ecx: (array int) = [1]
 112     68/push 1/imm32
 113     68/push 4/imm32/size
 114     89/<- %ecx 4/r32/esp
 115     # var edx: (array int) = []
 116     68/push 0/imm32/size
 117     89/<- %edx 4/r32/esp
 118     #
 119     (array-equal? %ecx %edx)  # => eax
 120     (check-ints-equal %eax 0 "F - test-compare-empty-with-non-empty-array")
 121     # . epilogue
 122     89/<- %esp 5/r32/ebp
 123     5d/pop-to-ebp
 124     c3/return
 125
 126 test-compare-equal-arrays:
 127     # . prologue
 128     55/push-ebp
 129     89/<- %ebp 4/r32/esp
 130     # var ecx: (array int) = [1, 2, 3]
 131     68/push 3/imm32
 132     68/push 2/imm32
 133     68/push 1/imm32
 134     68/push 0xc/imm32/size
 135     89/<- %ecx 4/r32/esp
 136     # var edx: (array int) = [1, 2, 3]
 137     68/push 3/imm32
 138     68/push 2/imm32
 139     68/push 1/imm32
 140     68/push 0xc/imm32/size
 141     89/<- %edx 4/r32/esp
 142     #
 143     (array-equal? %ecx %edx)  # => eax
 144     (check-ints-equal %eax 1 "F - test-compare-equal-arrays")
 145     # . epilogue
 146     89/<- %esp 5/r32/ebp
 147     5d/pop-to-ebp
 148     c3/return
 149
 150 test-compare-inequal-arrays-equal-sizes:
 151     # . prologue
 152     55/push-ebp
 153     89/<- %ebp 4/r32/esp
 154     # var ecx: (array int) = [1, 4, 3]
 155     68/push 3/imm32
 156     68/push 4/imm32
 157     68/push 1/imm32
 158     68/push 0xc/imm32/size
 159     89/<- %ecx 4/r32/esp
 160     # var edx: (array int) = [1, 2, 3]
 161     68/push 3/imm32
 162     68/push 2/imm32
 163     68/push 1/imm32
 164     68/push 0xc/imm32/size
 165     89/<- %edx 4/r32/esp
 166     #
 167     (array-equal? %ecx %edx)  # => eax
 168     (check-ints-equal %eax 0 "F - test-compare-inequal-arrays-equal-sizes")
 169     # . epilogue
 170     89/<- %esp 5/r32/ebp
 171     5d/pop-to-ebp
 172     c3/return
 173
 174 _parse-array-of-ints:  # ad: (addr allocation-descriptor), s: (addr array byte), out: (addr handle array int)
 175     # pseudocode
 176     #   end = &s->data[s->size]
 177     #   curr = s->data
 178     #   size = 0
 179     #   while true
 180     #     if (curr >= end) break
 181     #     curr = skip-chars-matching-in-slice(curr, end, ' ')
 182     #     if (curr >= end) break
 183     #     curr = skip-chars-not-matching-in-slice(curr, end, ' ')
 184     #     ++size
 185     #   allocate-array(ad, size*4, out)
 186     #   var slice: slice = {s->data, 0}
 187     #   curr = lookup(out)->data
 188     #   while true
 189     #     if (slice->start >= end) break
 190     #     slice->start = skip-chars-matching-in-slice(slice->start, end, ' ')
 191     #     if (slice->start >= end) break
 192     #     slice->end = skip-chars-not-matching-in-slice(slice->start, end, ' ')
 193     #     *curr = parse-hex-int-from-slice(slice)
 194     #     curr += 4
 195     #     slice->start = slice->end
 196     #   return result
 197     #
 198     # . prologue
 199     55/push-ebp
 200     89/<- %ebp 4/r32/esp
 201     # . save registers
 202     50/push-eax
 203     51/push-ecx
 204     52/push-edx
 205     53/push-ebx
 206     56/push-esi
 207     57/push-edi
 208     # esi = s
 209     8b/-> *(ebp+0xc) 6/r32/esi
 210     # var curr/ecx: (addr byte) = s->data
 211     8d/copy-address *(esi+4) 1/r32/ecx
 212     # var end/edx: (addr byte) = &s->data[s->size]
 213     # . edx = s->size
 214     8b/-> *esi 2/r32/edx
 215     # . edx += curr
 216     01/add-to %edx 1/r32/ecx
 217     # var size/ebx: int = 0
 218     31/xor-with %ebx 3/r32/ebx
 219 $_parse-array-of-ints:loop1:
 220     # if (curr >= end) break
 221     39/compare %ecx 2/r32/edx
 222     73/jump-if-addr>= $_parse-array-of-ints:break1/disp8
 223     # curr = skip-chars-matching-in-slice(curr, end, ' ')
 224     (skip-chars-matching-in-slice %ecx %edx 0x20)  # => eax
 225     89/<- %ecx 0/r32/eax
 226     # if (curr >= end) break
 227     39/compare %ecx 2/r32/edx
 228     73/jump-if-addr>= $_parse-array-of-ints:break1/disp8
 229     # curr = skip-chars-not-matching-in-slice(curr, end, ' ')
 230     (skip-chars-not-matching-in-slice %ecx %edx 0x20)  # => eax
 231     89/<- %ecx 0/r32/eax
 232     # size += 4
 233     81 0/subop/add %ebx 4/imm32
 234     eb/jump $_parse-array-of-ints:loop1/disp8
 235 $_parse-array-of-ints:break1:
 236     (allocate-array *(ebp+8) %ebx *(ebp+0x10))
 237 $_parse-array-of-ints:pass2:
 238     # var slice/edi: slice = {s->data, 0}
 239     68/push 0/imm32/end
 240     8d/copy-address *(esi+4) 7/r32/edi
 241     57/push-edi
 242     89/<- %edi 4/r32/esp
 243     # curr = lookup(out)->data
 244     8b/-> *(ebp+0x10) 0/r32/eax
 245     (lookup *eax *(eax+4))  # => eax
 246     8d/copy-address *(eax+4) 1/r32/ecx
 247 $_parse-array-of-ints:loop2:
 248     # if (slice->start >= end) break
 249     39/compare *edi 2/r32/edx
 250     73/jump-if-addr>= $_parse-array-of-ints:end/disp8
 251     # slice->start = skip-chars-matching-in-slice(slice->start, end, ' ')
 252     (skip-chars-matching-in-slice *edi %edx 0x20)  # => eax
 253     89/<- *edi 0/r32/eax
 254     # if (slice->start >= end) break
 255     39/compare *edi 2/r32/edx
 256     73/jump-if-addr>= $_parse-array-of-ints:end/disp8
 257     # slice->end = skip-chars-not-matching-in-slice(slice->start, end, ' ')
 258     (skip-chars-not-matching-in-slice *edi %edx 0x20)  # => eax
 259     89/<- *(edi+4) 0/r32/eax
 260     # *curr = parse-hex-int-from-slice(slice)
 261     (parse-hex-int-from-slice %edi)
 262     89/<- *ecx 0/r32/eax
 263     # curr += 4
 264     81 0/subop/add %ecx 4/imm32
 265     # slice->start = slice->end
 266     8b/-> *(edi+4) 0/r32/eax
 267     89/<- *edi 0/r32/eax
 268     eb/jump $_parse-array-of-ints:loop2/disp8
 269 $_parse-array-of-ints:end:
 270     # . reclaim locals
 271     81 0/subop/add %esp 8/imm32
 272     # . restore registers
 273     5f/pop-to-edi
 274     5e/pop-to-esi
 275     5b/pop-to-ebx
 276     5a/pop-to-edx
 277     59/pop-to-ecx
 278     58/pop-to-eax
 279     # . epilogue
 280     89/<- %esp 5/r32/ebp
 281     5d/pop-to-ebp
 282     c3/return
 283
 284 test-parse-array-of-ints:
 285     # . prologue
 286     55/push-ebp
 287     89/<- %ebp 4/r32/esp
 288     # var h/esi: (handle array int)
 289     68/push 0/imm32
 290     68/push 0/imm32
 291     89/<- %esi 4/r32/esp
 292     # var ecx: (array int) = [1, 2, 3]
 293     68/push 3/imm32
 294     68/push 2/imm32
 295     68/push 1/imm32
 296     68/push 0xc/imm32/size
 297     89/<- %ecx 4/r32/esp
 298     #
 299     (_parse-array-of-ints Heap "1 2 3" %esi)
 300     (lookup *esi *(esi+4))  # => eax
 301     (array-equal? %ecx %eax)  # => eax
 302     (check-ints-equal %eax 1 "F - test-parse-array-of-ints")
 303     # . epilogue
 304     89/<- %esp 5/r32/ebp
 305     5d/pop-to-ebp
 306     c3/return
 307
 308 test-parse-array-of-ints-empty:
 309     # - empty string = empty array
 310     # . prologue
 311     55/push-ebp
 312     89/<- %ebp 4/r32/esp
 313     # var h/esi: handle
 314     68/push 0/imm32
 315     68/push 0/imm32
 316     89/<- %esi 4/r32/esp
 317     #
 318     (_parse-array-of-ints Heap "" %esi)
 319     (lookup *esi *(esi+4))  # => eax
 320     (check-ints-equal *eax 0 "F - test-parse-array-of-ints-empty")
 321     # . epilogue
 322     89/<- %esp 5/r32/ebp
 323     5d/pop-to-ebp
 324     c3/return
 325
 326 test-parse-array-of-ints-just-whitespace:
 327     # - just whitespace = empty array
 328     # . prologue
 329     55/push-ebp
 330     89/<- %ebp 4/r32/esp
 331     # var h/esi: handle
 332     68/push 0/imm32
 333     68/push 0/imm32
 334     89/<- %esi 4/r32/esp
 335     #
 336     (_parse-array-of-ints Heap Space %esi)
 337     (lookup *esi *(esi+4))  # => eax
 338     (check-ints-equal *eax 0 "F - test-parse-array-of-ints-just-whitespace")
 339     # . epilogue
 340     89/<- %esp 5/r32/ebp
 341     5d/pop-to-ebp
 342     c3/return
 343
 344 test-parse-array-of-ints-extra-whitespace:
 345     # . prologue
 346     55/push-ebp
 347     89/<- %ebp 4/r32/esp
 348     # var h/esi: handle
 349     68/push 0/imm32
 350     68/push 0/imm32
 351     89/<- %esi 4/r32/esp
 352     # var ecx: (array int) = [1, 2, 3]
 353     68/push 3/imm32
 354     68/push 2/imm32
 355     68/push 1/imm32
 356     68/push 0xc/imm32/size
 357     89/<- %ecx 4/r32/esp
 358     #
 359     (_parse-array-of-ints Heap " 1 2  3  " %esi)
 360     (lookup *esi *(esi+4))  # => eax
 361     (array-equal? %ecx %eax)  # => eax
 362     (check-ints-equal %eax 1 "F - test-parse-array-of-ints-extra-whitespace")
 363     # . epilogue
 364     89/<- %esp 5/r32/ebp
 365     5d/pop-to-ebp
 366     c3/return
 367
 368 parse-array-of-ints:  # s: (addr array byte), out: (addr handle array int)
 369     # . prologue
 370     55/push-ebp
 371     89/<- %ebp 4/r32/esp
 372     #
 373     (_parse-array-of-ints Heap *(ebp+8) *(ebp+0xc))
 374 $parse-array-of-ints:end:
 375     # . epilogue
 376     89/<- %esp 5/r32/ebp
 377     5d/pop-to-ebp
 378     c3/return
 379
 380 # helper for later tests
 381 # compare an array with a string representation of an array literal
 382 check-array-equal:  # a: (addr array int), expected: (addr string), msg: (addr string)
 383     # . prologue
 384     55/push-ebp
 385     89/<- %ebp 4/r32/esp
 386     # . save registers
 387     50/push-eax
 388     56/push-esi
 389     # var h/esi: handle
 390     68/push 0/imm32
 391     68/push 0/imm32
 392     89/<- %esi 4/r32/esp
 393     # var b/eax: (addr array int) = parse-array-of-ints(Heap, expected)
 394     (parse-array-of-ints *(ebp+0xc) %esi)
 395     (lookup *esi *(esi+4))  # => eax
 396     #
 397     (array-equal? *(ebp+8) %eax)
 398     (check-ints-equal %eax 1 *(ebp+0x10))
 399 $check-array-equal:end:
 400     # . restore registers
 401     5e/pop-to-esi
 402     58/pop-to-eax
 403     # . epilogue
 404     89/<- %esp 5/r32/ebp
 405     5d/pop-to-ebp
 406     c3/return
 407
 408 test-check-array-equal:
 409     # . prologue
 410     55/push-ebp
 411     89/<- %ebp 4/r32/esp
 412     # var ecx: (array int) = [1, 2, 3]
 413     68/push 3/imm32
 414     68/push 2/imm32
 415     68/push 1/imm32
 416     68/push 0xc/imm32/size
 417     89/<- %ecx 4/r32/esp
 418     #
 419     (check-array-equal %ecx "1 2 3" "F - test-check-array-equal")
 420     # . epilogue
 421     89/<- %esp 5/r32/ebp
 422     5d/pop-to-ebp
 423     c3/return
 424
 425 == data
 426
 427 # length-prefixed string containing just a single space
 428 Space:  # (array byte)
 429     # size: int
 430     1/imm32
 431     # data
 432     20/space