Saturday, January 5, 2013

Negative modulo's

This function from http://qugstart.com/blog/ruby-and-rails/facebook-base64-url-decode-for-signed_request/ basically tries to add extra padding characters before attempting to base64-decode a string:

  # Pad the encoded string with "+".
  data += "=" * (4 - (len(data) % 4) % 4)
  return base64.urlsafe_b64decode(data)

Django has the equivalent function in its django.core.signing library:

def b64_decode(s):
    pad = '=' * (-len(s) % 4)
    return base64.urlsafe_b64decode(s + pad)
The code from Django's function uses negative modulo to compute the vaule. How do negative modulos work?    See this excerpt from http://mathforum.org/library/drmath/view/52343.html:

The mod function is defined as the amount by which a number exceeds the 
largest integer multiple of the divisor that is not greater than that 
number. In this case, -340 lies between -360 and -300, so -360 is the 
greatest multiple LESS than -340; we subtract 60 * -6 = -360 from -340 
and get 20:

-420 -360 -300 -240 -180 -120  -60   0   60   120  180  240  300  360
--+----+----+----+----+----+----+----+----+----+----+----+----+----+--
       | |                                                    |  |
   -360| |-340                                             300|  |340
       |=|                                                    |==|
        20                                                     40

Working with a positive number like 340, the multiple we subtract is 
smaller in absolute value, giving us 40; but with negative numbers, we 
subtract a number with a LARGER absolute value, so that the mod 
function returns a positive value. This is not always what people 
expect, but it is consistent.

If you want the remainder, ignoring the sign, you have to take the 
absolute value before using the mod function.

1 comment: