search

ruricolist / serapeum

Utilities beyond Alexandria
MIT License
425 stars 42 forks source link

Array Length Miscalculation for RANGE & Buffer Overflow #50

Closed ramenbytes closed 4 years ago

ramenbytes commented 4 years ago

Sorry if this is a bit terse, I'm pressed for time and wanted to get this written before I forgot. If I'm mistaken about something just let me know.

Expected: (range -2 5 2) => #(-2 0 2 4) Actual: (range -2 5 2) => #(-2 0 2)

The length is calcuated by int-range-shape, on line 127 of range.lisp in a let binding:

(len (abs (truncate (- high low) step)))

If (mod (- high low) step) is not zero we end up one short in our calculation of the range's number of elements.

While I haven't exhaustively tested it, the following snippet seems to correctly calculate the length:

(multiple-value-bind (quotient remainder)
    (truncate (- high low) step)
  (if (zerop remainder)
      (abs quotient)
      (1+ (abs quotient))))

Related to this, fill-int-range! iterates over the proper length of the array, resulting in an array bounds condition on SBCL 2.0.1 if I recompile the function without the #.no-bounds-checks declaration. I think it without bounds checks it just overflows the array.

ruricolist commented 4 years ago

Thanks for this. Since rounding up is the correct behavior I just changed it from truncate to ceiling (and added a regression test).

ramenbytes commented 4 years ago

Cool! I knew there had to be an easier way than m-v-b.