https://github.com/akkartik/mu/blob/master/100array-equal.subx
  1 # Comparing arrays of numbers.
  2 
  3 == code
  4 
  5 array-equal?:  # a: (addr array int), b: (addr array int) -> eax: boolean
  6     # pseudocode:
  7     #   lena = a->length
  8     #   if (lena != b->length) return false
  9     #   i = 0
 10     #   curra = a->data
 11     #   currb = b->data
 12     #   while i < lena
 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     #   lena: 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 lena/edx: int = a->length
 41     8b/-> *esi 2/r32/edx
 42 $array-equal?:lengths:
 43     # if (lena != b->length) 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 %ecx 1/r32/ecx
 52     # var vala/eax: int
 53     # var valb/ebx: int
 54 $array-equal?:loop:
 55     # if (i >= lena) 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     # eax = array-equal?(ecx, edx)
100     # . . push args
101     52/push-edx
102     51/push-ecx
103     # . . call
104     e8/call array-equal?/disp32
105     # . . discard args
106     81 0/subop/add %esp 8/imm32
107     # check-ints-equal(eax, 1, msg)
108     # . . push args
109     68/push "F - test-compare-empty-with-empty-array"/imm32
110     68/push 1/imm32/true
111     50/push-eax
112     # . . call
113     e8/call check-ints-equal/disp32
114     # . . discard args
115     81 0/subop/add %esp 0xc/imm32
116     # . epilogue
117     89/<- %esp 5/r32/ebp
118     5d/pop-to-ebp
119     c3/return
120 
121 test-compare-empty-with-non-empty-array:  # also checks length-mismatch code path
122     # . prologue
123     55/push-ebp
124     89/<- %ebp 4/r32/esp
125     # var ecx: (array int) = [1]
126     68/push 1/imm32
127     68/push 4/imm32/size
128     89/<- %ecx 4/r32/esp
129     # var edx: (array int) = []
130     68/push 0/imm32/size
131     89/<- %edx 4/r32/esp
132     # eax = array-equal?(ecx, edx)
133     # . . push args
134     52/push-edx
135     51/push-ecx
136     # . . call
137     e8/call array-equal?/disp32
138     # . . discard args
139     81 0/subop/add %esp 8/imm32
140     # check-ints-equal(eax, 0, msg)
141     # . . push args
142     68/push "F - test-compare-empty-with-non-empty-array"/imm32
143     68/push 0/imm32/false
144     50/push-eax
145     # . . call
146     e8/call check-ints-equal/disp32
147     # . . discard args
148     81 0/subop/add %esp 0xc/imm32
149     # . epilogue
150     89/<- %esp 5/r32/ebp
151     5d/pop-to-ebp
152     c3/return
153 
154 test-compare-equal-arrays:
155     # . prologue
156     55/push-ebp
157     89/<- %ebp 4/r32/esp
158     # var ecx: (array int) = [1, 2, 3]
159     68/push 3/imm32
160     68/push 2/imm32
161     68/push 1/imm32
162     68/push 0xc/imm32/size
163     89/<- %ecx 4/r32/esp
164     # var edx: (array int) = [1, 2, 3]
165     68/push 3/imm32
166     68/push 2/imm32
167     68/push 1/imm32
168     68/push 0xc/imm32/size
169     89/<- %edx 4/r32/esp
170     # eax = array-equal?(ecx, edx)
171     # . . push args
172     52/push-edx
173     51/push-ecx
174     # . . call
175     e8/call array-equal?/disp32
176     # . . discard args
177     81 0/subop/add %esp 8/imm32
178     # check-ints-equal(eax, 1, msg)
179     # . . push args
180     68/push "F - test-compare-equal-arrays"/imm32
181     68/push 1/imm32/true
182     50/push-eax
183     # . . call
184     e8/call check-ints-equal/disp32
185     # . . discard args
186     81 0/subop/add %esp 0xc/imm32
187     # . epilogue
188     89/<- %esp 5/r32/ebp
189     5d/pop-to-ebp
190     c3/return
191 
192 test-compare-inequal-arrays-equal-lengths:
193     # . prologue
194     55/push-ebp
195     89/<- %ebp 4/r32/esp
196     # var ecx: (array int) = [1, 4, 3]
197     68/push 3/imm32
198     68/push 4/imm32
199     68/push 1/imm32
200     68/push 0xc/imm32/size
201     89/<- %ecx 4/r32/esp
202     # var edx: (array int) = [1, 2, 3]
203     68/push 3/imm32
204     68/push 2/imm32
205     68/push 1/imm32
206     68/push 0xc/imm32/size
207     89/<- %edx 4/r32/esp
208     # eax = array-equal?(ecx, edx)
209     # . . push args
210     52/push-edx
211     51/push-ecx
212     # . . call
213     e8/call array-equal?/disp32
214     # . . discard args
215     81 0/subop/add %esp 8/imm32
216     # check-ints-equal(eax, 0, msg)
217     # . . push args
218     68/push "F - test-compare-inequal-arrays-equal-lengths"/imm32
219     68/push 0/imm32/false
220     50/push-eax
221     # . . call
222     e8/call check-ints-equal/disp32
223     # . . discard args
224     81 0/subop/add %esp 0xc/imm32
225     # . epilogue
226     89/<- %esp 5/r32/ebp
227     5d/pop-to-ebp
228     c3/return
229 
230 parse-array-of-ints:  # ad: (addr allocation-descriptor), s: (addr string) -> result/eax: (handle array int)
231     # pseudocode
232     #   end = &s->data[s->length]
233     #   curr = s->data
234     #   size = 0
235     #   while true
236     #     if (curr >= end) break
237     #     curr = skip-chars-matching-in-slice(curr, end, ' ')
238     #     if (curr >= end) break
239     #     curr = skip-chars-not-matching-in-slice(curr, end, ' ')
240     #     ++size
241     #   result = allocate(ad, (size+1)*4)
242     #   result->size = (size+1)*4
243     #   var slice: slice = {s->data, 0}
244     #   out = result->data
245     #   while true
246     #     if (slice->start >= end) break
247     #     slice->start = skip-chars-matching-in-slice(slice->start, end, ' ')
248     #     if (slice->start >= end) break
249     #     slice->end = skip-chars-not-matching-in-slice(slice->start, end, ' ')
250     #     *out = parse-hex-int-from-slice(slice)
251     #     out += 4
252     #     slice->start = slice->end
253     #   return result
254     #
255     # . prologue
256     55/push-ebp
257     89/<- %ebp 4/r32/esp
258     # . save registers
259     51/push-ecx
260     52/push-edx
261     53/push-ebx
262     56/push-esi
263     57/push-edi
264     # esi = s
265     8b/-> *(ebp+0xc) 6/r32/esi
266     # var curr/ecx: (addr byte) = s->data
267     8d/copy-address *(esi+4) 1/r32/ecx
268     # var end/edx: (addr byte) = &s->data[s->length]
269     # . edx = s->length
270     8b/-> *esi 2/r32/edx
271     # . edx += curr
272     01/add %edx 1/r32/ecx
273     # var size/ebx: int = 0
274     31/xor %ebx 3/r32/ebx
275 $parse-array-of-ints:loop1:
276     # if (curr >= end) break
277     39/compare %ecx 2/r32/edx
278     73/jump-if-addr>= $parse-array-of-ints:break1/disp8
279     # curr = skip-chars-matching-in-slice(curr, end, ' ')
280     # . eax = skip-chars-matching-in-slice(curr, end, ' ')
281     # . . push args
282     68/push 0x20/imm32/space
283     52/push-edx
284     51/push-ecx
285     # . . call
286     e8/call skip-chars-matching-in-slice/disp32
287     # . . discard args
288     81 0/subop/add %esp 0xc/imm32
289     # . ecx = eax
290     89/<- %ecx 0/r32/eax
291     # if (curr >= end) break
292     39/compare %ecx 2/r32/edx
293     73/jump-if-addr>= $parse-array-of-ints:break1/disp8
294     # curr = skip-chars-not-matching-in-slice(curr, end, ' ')
295     # . eax = skip-chars-not-matching-in-slice(curr, end, ' ')
296     # . . push args
297     68/push 0x20/imm32/space
298     52/push-edx
299     51/push-ecx
300     # . . call
301     e8/call skip-chars-not-matching-in-slice/disp32
302     # . . discard args
303     81 0/subop/add %esp 0xc/imm32
304     # . ecx = eax
305     89/<- %ecx 0/r32/eax
306     # size += 4
307     81 0/subop/add %ebx 4/imm32
308     eb/jump $parse-array-of-ints:loop1/disp8
309 $parse-array-of-ints:break1:
310     # var result/edi: (handle array int) = allocate(ad, size+4)
311     # . eax = allocate(ad, size+4)
312     # . . push args
313     89/<- %eax 3/r32/ebx
314     05/add-to-eax 4/imm32
315     50/push-eax
316     ff 6/subop/push *(ebp+8)
317     # . . call
318     e8/call allocate/disp32
319     # . . discard args
320     81 0/subop/add %esp 8/imm32
321     # . edi = eax
322     89/<- %edi 0/r32/eax
323     # result->size = size
324     89/<- *eax 3/r32/ebx
325 $parse-array-of-ints:pass2:
326     # var slice/ecx: slice = {s->data, 0}
327     68/push 0/imm32/end
328     8d/copy-address *(esi+4) 1/r32/ecx
329     51/push-ecx
330     89/<- %ecx 4/r32/esp
331     # var out/ebx: (addr byte) = result->data
332     8d/copy-address *(eax+4) 3/r32/ebx
333 $parse-array-of-ints:loop2:
334     # if (slice->start >= end) break
335     39/compare *ecx 2/r32/edx
336     73/jump-if-addr>= $parse-array-of-ints:end/disp8
337     # slice->start = skip-chars-matching-in-slice(slice->start, end, ' ')
338     # . eax = skip-chars-matching-in-slice(slice->start, end, ' ')
339     # . . push args
340     68/push 0x20/imm32/space
341     52/push-edx
342     ff 6/subop/push *ecx
343     # . . call
344     e8/call skip-chars-matching-in-slice/disp32
345     # . . discard args
346     81 0/subop/add %esp 0xc/imm32
347     # . slice->start = eax
348     89/<- *ecx 0/r32/eax
349     # if (slice->start >= end) break
350     39/compare *ecx 2/r32/edx
351     73/jump-if-addr>= $parse-array-of-ints:end/disp8
352     # slice->end = skip-chars-not-matching-in-slice(slice->start, end, ' ')
353     # . eax = skip-chars-not-matching-in-slice(curr, end, ' ')
354     # . . push args
355     68/push 0x20/imm32/space
356     52/push-edx
357     50/push-eax
358     # . . call
359     e8/call skip-chars-not-matching-in-slice/disp32
360     # . . discard args
361     81 0/subop/add %esp 0xc/imm32
362     # . slice->end = eax
363     89/<- *(ecx+4) 0/r32/eax
364     # *out = parse-hex-int-from-slice(slice)
365     # . eax = parse-hex-int-from-slice(slice)
366     # . . push args
367     51/push-ecx
368     # . . call
369     e8/call parse-hex-int-from-slice/disp32
370     # . . discard args
371     81 0/subop/add %esp 4/imm32
372     # . *out = eax
373     89/<- *ebx 0/r32/eax
374     # out += 4
375     81 0/subop/add %ebx 4/imm32
376     # slice->start = slice->end
377     8b/-> *(ecx+4) 0/r32/eax
378     89/<- *ecx 0/r32/eax
379     81 0/subop/add %ecx 4/imm32
380     eb/jump $parse-array-of-ints:loop2/disp8
381 $parse-array-of-ints:end:
382     # return edi
383     89/<- %eax 7/r32/edi
384     # . reclaim locals
385     81 0/subop/add %esp 8/imm32
386     # . restore registers
387     5f/pop-to-edi
388     5e/pop-to-esi
389     5b/pop-to-ebx
390     5a/pop-to-edx
391     59/pop-to-ecx
392     # . epilogue
393     89/<- %esp 5/r32/ebp
394     5d/pop-to-ebp
395     c3/return
396 
397 test-parse-array-of-ints:
398     # . prologue
399     55/push-ebp
400     89/<- %ebp 4/r32/esp
401     # var ecx: (array int) = [1, 2, 3]
402     68/push 3/imm32
403     68/push 2/imm32
404     68/push 1/imm32
405     68/push 0xc/imm32/size
406     89/<- %ecx 4/r32/esp
407     # eax = parse-array-of-ints(Heap, "1 2 3")
408     # . . push args
409     68/push "1 2 3"/imm32
410     68/push Heap/imm32
411     # . . call
412     e8/call parse-array-of-ints/disp32
413     # . . discard args
414     81 0/subop/add %esp 8/imm32
415     # eax = array-equal?(ecx, eax)
416     # . . push args
417     50/push-eax
418     51/push-ecx
419     # . . call
420     e8/call array-equal?/disp32
421     # . . discard args
422     81 0/subop/add %esp 8/imm32
423     # check-ints-equal(eax, 1, msg)
424     # . . push args
425     68/push "F - test-parse-array-of-ints"/imm32
426     68/push 1/imm32/true
427     50/push-eax
428     # . . call
429     e8/call check-ints-equal/disp32
430     # . . discard args
431     81 0/subop/add %esp 0xc/imm32
432     # . epilogue
433     89/<- %esp 5/r32/ebp
434     5d/pop-to-ebp
435     c3/return
436 
437 test-parse-array-of-ints-empty:
438     # - empty string = empty array
439     # . prologue
440     55/push-ebp
441     89/<- %ebp 4/r32/esp
442     # eax = parse-array-of-ints(Heap, "")
443     # . . push args
444     68/push ""/imm32
445     68/push Heap/imm32
446     # . . call
447     e8/call parse-array-of-ints/disp32
448     # . . discard args
449     81 0/subop/add %esp 8/imm32
450     # check-ints-equal(*eax, 0, msg)
451     # . . push args
452     68/push "F - test-parse-array-of-ints-empty"/imm32
453     68/push 0/imm32/size
454     ff 6/subop/push *eax
455     # . . call
456     e8/call check-ints-equal/disp32
457     # . . discard args
458     81 0/subop/add %esp 0xc/imm32
459     # . epilogue
460     89/<- %esp 5/r32/ebp
461     5d/pop-to-ebp
462     c3/return
463 
464 test-parse-array-of-ints-just-whitespace:
465     # - just whitespace = empty array
466     # . prologue
467     55/push-ebp
468     89/<- %ebp 4/r32/esp
469     # eax = parse-array-of-ints(Heap, " ")
470     # . . push args
471     68/push Space/imm32
472     68/push Heap/imm32
473     # . . call
474     e8/call parse-array-of-ints/disp32
475     # . . discard args
476     81 0/subop/add %esp 8/imm32
477     # check-ints-equal(*eax, 0, msg)
478     # . . push args
479     68/push "F - test-parse-array-of-ints-empty"/imm32
480     68/push 0/imm32/size
481     ff 6/subop/push *eax
482     # . . call
483     e8/call check-ints-equal/disp32
484     # . . discard args
485     81 0/subop/add %esp 0xc/imm32
486     # . epilogue
487     89/<- %esp 5/r32/ebp
488     5d/pop-to-ebp
489     c3/return
490 
491 test-parse-array-of-ints-extra-whitespace:
492     # . prologue
493     55/push-ebp
494     89/<- %ebp 4/r32/esp
495     # var ecx: (array int) = [1, 2, 3]
496     68/push 3/imm32
497     68/push 2/imm32
498     68/push 1/imm32
499     68/push 0xc/imm32/size
500     89/<- %ecx 4/r32/esp
501     # eax = parse-array-of-ints(Heap, " 1 2  3  ")
502     # . . push args
503     68/push " 1 2  3  "/imm32
504     68/push Heap/imm32
505     # . . call
506     e8/call parse-array-of-ints/disp32
507     # . . discard args
508     81 0/subop/add %esp 8/imm32
509     # eax = array-equal?(ecx, eax)
510     # . . push args
511     50/push-eax
512     51/push-ecx
513     # . . call
514     e8/call array-equal?/disp32
515     # . . discard args
516     81 0/subop/add %esp 8/imm32
517     # check-ints-equal(eax, 1, msg)
518     # . . push args
519     68/push "F - test-parse-array-of-ints-extra-whitespace"/imm32
520     68/push 1/imm32/true
521     50/push-eax
522     # . . call
523     e8/call check-ints-equal/disp32
524     # . . discard args
525     81 0/subop/add %esp 0xc/imm32
526     # . epilogue
527     89/<- %esp 5/r32/ebp
528     5d/pop-to-ebp
529     c3/return
530 
531 # helper for later tests
532 # compare an array with a string representation of an array literal
533 check-array-equal:  # a: (addr array int), expected: (addr string), msg: (addr string)
534     # . prologue
535     55/push-ebp
536     89/<- %ebp 4/r32/esp
537     # . save registers
538     50/push-eax
539     # var b/ecx: (handle array int) = parse-array-of-ints(Heap, expected)
540     # . eax = parse-array-of-ints(Heap, expected)
541     # . . push args
542     ff 6/subop/push *(ebp+0xc)
543     68/push Heap/imm32
544     # . . call
545     e8/call parse-array-of-ints/disp32
546     # . . discard args
547     81 0/subop/add %esp 8/imm32
548     # . b = eax
549     89/<- %ecx 0/r32/eax
550     # eax = array-equal?(a, b)
551     # . . push args
552     51/push-ecx
553     ff 6/subop/push *(ebp+8)
554     # . . call
555     e8/call array-equal?/disp32
556     # . . discard args
557     81 0/subop/add %esp 8/imm32
558     # check-ints-equal(eax, 1, msg)
559     # . . push args
560     ff 6/subop/push *(ebp+0x10)
561     68/push 1/imm32
562     50/push-eax
563     # . . call
564     e8/call check-ints-equal/disp32
565     # . . discard args
566     81 0/subop/add %esp 0xc/imm32
567 $check-array-equal:end:
568     # . restore registers
569     58/pop-to-eax
570     # . epilogue
571     89/<- %esp 5/r32/ebp
572     5d/pop-to-ebp
573     c3/return
574 
575 test-check-array-equal:
576     # . prologue
577     55/push-ebp
578     89/<- %ebp 4/r32/esp
579     # var ecx: (array int) = [1, 2, 3]
580     68/push 3/imm32
581     68/push 2/imm32
582     68/push 1/imm32
583     68/push 0xc/imm32/size
584     89/<- %ecx 4/r32/esp
585     # check-array-equal(ecx, "1 2 3", "msg")
586     # . . push args
587     68/push "F - test-check-array-equal"/imm32
588     68/push "1 2 3"/imm32
589     51/push-ecx
590     # . . call
591     e8/call check-array-equal/disp32
592     # . . discard args
593     81 0/subop/add %esp 8/imm32
594     # . epilogue
595     89/<- %esp 5/r32/ebp
596     5d/pop-to-ebp
597     c3/return
598 
599 # . . vim:nowrap:textwidth=0