encode transposed bytes

=======================
* replaced h64.encode_xxx_offsets() functions with h64.encode_transposed_bytes() and list of offsets
* affects sha256-crypt, sha512-crypt, md5-crypt, sun-md5-crypt

8 files changed, 266 insertions, 141 deletions

diff --git a/docs/lib/passlib.utils.h64.rst b/docs/lib/passlib.utils.h64.rst
index 0475f34..e467508 100644
--- a/docs/lib/passlib.utils.h64.rst
+++ b/docs/lib/passlib.utils.h64.rst
@@ -33,9 +33,10 @@ Bytes <-> Hash64
 ================
 
 .. autofunction:: encode_bytes
-.. autofunction:: encode_3_offsets
-.. autofunction:: encode_2_offsets
-.. autofunction:: encode_1_offset
+.. autofunction:: decode_bytes
+
+.. autofunction:: encode_transposed_bytes
+.. autofunction:: decode_transposed_bytes
 
 Int <-> Hash64
 ==============
diff --git a/passlib/base.py b/passlib/base.py
index 65a23bd..03d3ad3 100644
--- a/passlib/base.py
+++ b/passlib/base.py
@@ -268,7 +268,7 @@ class CryptContext(object):
             raise ValueError, "no schemes defined"
         if isinstance(schemes, str):
             schemes = splitcomma(schemes)
-        for scheme in reversed(schemes): #NOTE: reversed() just so last entry is used as default.
+        for scheme in reversed(schemes): #NOTE: reversed() just so last entry is used as default, and is checked first.
             self._add_scheme(scheme)
 
         #parse deprecated set
diff --git a/passlib/hash/md5_crypt.py b/passlib/hash/md5_crypt.py
index 986ff04..21262be 100644
--- a/passlib/hash/md5_crypt.py
+++ b/passlib/hash/md5_crypt.py
@@ -107,16 +107,16 @@ def raw_md5_crypt(secret, salt, apr=False):
         result = h.digest()
 
     #encode resulting hash
-    out = ''.join(
-        h64.encode_3_offsets(result,
-            idx+12 if idx < 4 else 5,
-            idx+6,
-            idx,
-        )
-        for idx in xrange(5)
-        ) + h64.encode_1_offset(result, 11)
-
-    return out
+    return h64.encode_transposed_bytes(result, _chk_offsets)
+
+_chk_offsets = (
+    12,6,0,
+    13,7,1,
+    14,8,2,
+    15,9,3,
+    5,10,4,
+    11,
+)
 
 #=========================================================
 #choose backend
diff --git a/passlib/hash/sha256_crypt.py b/passlib/hash/sha256_crypt.py
index ddff536..9fdd5c4 100644
--- a/passlib/hash/sha256_crypt.py
+++ b/passlib/hash/sha256_crypt.py
@@ -3,7 +3,7 @@
 #imports
 #=========================================================
 #core
-from hashlib import sha256, sha512
+from hashlib import sha256
 import re
 import logging; log = logging.getLogger(__name__)
 from warnings import warn
@@ -151,33 +151,23 @@ def raw_sha256_crypt(secret, salt, rounds):
     "perform raw sha256-crypt; returns encoded checksum, normalized salt & rounds"
     #run common crypt routine
     result, salt, rounds = raw_sha_crypt(secret, salt, rounds, sha256)
-
-    #encode result
-    out = ''
-    a, b, c = 0, 10, 20
-    while a < 30:
-        out += h64.encode_3_offsets(result, c, b, a)
-        a, b, c = c+1, a+1, b+1
-    assert a == 30, "loop went to far: %r" % (a,)
-    out += h64.encode_2_offsets(result, 30, 31)
+    out = h64.encode_transposed_bytes(result, _256_offsets)
     assert len(out) == 43, "wrong length: %r" % (out,)
     return out, salt, rounds
 
-def raw_sha512_crypt(secret, salt, rounds):
-    "perform raw sha512-crypt; returns encoded checksum, normalized salt & rounds"
-    #run common crypt routine
-    result, salt, rounds = raw_sha_crypt(secret, salt, rounds, sha512)
-
-    #encode result
-    out = ''
-    a, b, c = 0, 21, 42
-    while c < 63:
-        out += h64.encode_3_offsets(result, c, b, a)
-        a, b, c = b+1, c+1, a+1
-    assert c == 63, "loop to far: %r" % (c,)
-    out += h64.encode_1_offset(result, 63)
-    assert len(out) == 86, "wrong length: %r" % (out,)
-    return out, salt, rounds
+_256_offsets = (
+    20, 10, 0,
+    11, 1,  21,
+    2,  22, 12,
+    23, 13, 3,
+    14, 4,  24,
+    5,  25, 15,
+    26, 16, 6,
+    17, 7,  27,
+    8,  28, 18,
+    29, 19, 9,
+    30, 31,
+)
 
 #=========================================================
 #choose backend
diff --git a/passlib/hash/sha512_crypt.py b/passlib/hash/sha512_crypt.py
index 4001b6f..59bc285 100644
--- a/passlib/hash/sha512_crypt.py
+++ b/passlib/hash/sha512_crypt.py
@@ -8,14 +8,14 @@ for any handler specific details.
 #imports
 #=========================================================
 #core
-from hashlib import sha256
+from hashlib import sha512
 import re
 import logging; log = logging.getLogger(__name__)
 from warnings import warn
 #site
 #libs
 from passlib.utils import norm_rounds, norm_salt, h64, autodocument
-from passlib.hash.sha256_crypt import raw_sha512_crypt
+from passlib.hash.sha256_crypt import raw_sha_crypt
 #pkg
 #local
 __all__ = [
@@ -27,6 +27,44 @@ __all__ = [
 ]
 
 #=========================================================
+#builtin backend
+#=========================================================
+def raw_sha512_crypt(secret, salt, rounds):
+    "perform raw sha512-crypt; returns encoded checksum, normalized salt & rounds"
+    #run common crypt routine
+    result, salt, rounds = raw_sha_crypt(secret, salt, rounds, sha512)
+
+    ###encode result
+    out = h64.encode_transposed_bytes(result, _512_offsets)
+    assert len(out) == 86, "wrong length: %r" % (out,)
+    return out, salt, rounds
+
+_512_offsets = (
+    42, 21, 0,
+    1,  43, 22,
+    23, 2,  44,
+    45, 24, 3,
+    4,  46, 25,
+    26, 5,  47,
+    48, 27, 6,
+    7,  49, 28,
+    29, 8,  50,
+    51, 30, 9,
+    10, 52, 31,
+    32, 11, 53,
+    54, 33, 12,
+    13, 55, 34,
+    35, 14, 56,
+    57, 36, 15,
+    16, 58, 37,
+    38, 17, 59,
+    60, 39, 18,
+    19, 61, 40,
+    41, 20, 62,
+    63,
+)
+
+#=========================================================
 #choose backend
 #=========================================================
 
@@ -47,6 +85,7 @@ else:
     else:
         crypt = None
 
+crypt = None
 #=========================================================
 #algorithm information
 #=========================================================
@@ -72,9 +111,9 @@ _pat = re.compile(r"""
     (\$rounds=(?P<rounds>\d+))?
     \$
     (
-        (?P<salt1>[^:$]*)
+        (?P<salt1>[^:$\n]*)
         |
-        (?P<salt2>[^:$]{0,16})
+        (?P<salt2>[^:$\n]{0,16})
         \$
         (?P<chk>[A-Za-z0-9./]{86})?
     )
diff --git a/passlib/hash/sun_md5_crypt.py b/passlib/hash/sun_md5_crypt.py
index 9933bc0..8db54ba 100644
--- a/passlib/hash/sun_md5_crypt.py
+++ b/passlib/hash/sun_md5_crypt.py
@@ -175,16 +175,17 @@ def raw_sun_md5_crypt(secret, rounds, salt):
         round += 1
 
     #encode output
-    #NOTE: appears to use same output encoding as md5-crypt
-    out = ''.join(
-        h64.encode_3_offsets(result,
-            idx+12 if idx < 4 else 5,
-            idx+6,
-            idx,
-        )
-        for idx in xrange(5)
-        ) + h64.encode_1_offset(result, 11)
-    return out
+    return h64.encode_transposed_bytes(result, _chk_offsets)
+
+#NOTE: same offsets as md5_crypt
+_chk_offsets = (
+    12,6,0,
+    13,7,1,
+    14,8,2,
+    15,9,3,
+    5,10,4,
+    11,
+)
 
 #=========================================================
 #algorithm information
diff --git a/passlib/tests/test_utils.py b/passlib/tests/test_utils.py
index 8f8659e..0eec054 100644
--- a/passlib/tests/test_utils.py
+++ b/passlib/tests/test_utils.py
@@ -164,32 +164,85 @@ class H64_Test(TestCase):
     "test H64 codec functions"
     case_prefix = "H64 codec"
 
-    def test_encode_1_offset(self):
-        self.assertFunctionResults(h64.encode_1_offset,[
-            ("z1", "\xff", 0),
-            ("..", "\x00", 0),
-        ])
-
-    def test_encode_2_offsets(self):
-        self.assertFunctionResults(h64.encode_2_offsets,[
-            (".wD", "\x00\xff", 0, 1),
-            ("z1.", "\xff\x00", 0, 1),
-            ("z1.", "\x00\xff", 1, 0),
-        ])
-
-    def test_encode_3_offsets(self):
-        self.assertFunctionResults(h64.encode_3_offsets,[
-            #move through each byte, keep offsets
-            ("..kz", "\x00\x00\xff", 0, 1, 2),
-            (".wD.", "\x00\xff\x00", 0, 1, 2),
-            ("z1..", "\xff\x00\x00", 0, 1, 2),
-
-            #move through each offset, keep bytes
-            (".wD.", "\x00\x00\xff", 0, 2, 1),
-            ("z1..", "\x00\x00\xff", 2, 0, 1),
-        ])
+    #=========================================================
+    #test basic encode/decode
+    #=========================================================
+    encoded_bytes = [
+        #test lengths 0..6 to ensure tail is encoded properly
+        ("",""),
+        ("\x55","J/"),
+        ("\x55\xaa","Jd8"),
+        ("\x55\xaa\x55","JdOJ"),
+        ("\x55\xaa\x55\xaa","JdOJe0"),
+        ("\x55\xaa\x55\xaa\x55","JdOJeK3"),
+        ("\x55\xaa\x55\xaa\x55\xaa","JdOJeKZe"),
 
+        #test padding bits are null
+        ("\x55\xaa\x55\xaf","JdOJj0"), # len = 1 mod 3
+        ("\x55\xaa\x55\xaa\x5f","JdOJey3"), # len = 2 mod 3
+    ]
+
+    decode_padding_bytes = [
+        #len = 2 mod 4 -> 2 msb of last digit is padding
+        ("..", "\x00"), # . = h64.CHARS[0b000000]
+        (".0", "\x80"), # 0 = h64.CHARS[0b000010]
+        (".2", "\x00"), # 2 = h64.CHARS[0b000100]
+        (".U", "\x00"), # U = h64.CHARS[0b100000]
+
+        #len = 3 mod 4 -> 4 msb of last digit is padding
+        ("...", "\x00\x00"),
+        ("..6", "\x00\x80"), # 6 = h64.CHARS[0b001000]
+        ("..E", "\x00\x00"), # E = h64.CHARS[0b010000]
+        ("..U", "\x00\x00"),
+    ]
+
+    def test_encode_bytes(self):
+        for source, result in self.encoded_bytes:
+            out = h64.encode_bytes(source)
+            self.assertEqual(out, result)
+
+    def test_decode_bytes(self):
+        for result, source in self.encoded_bytes:
+            out = h64.decode_bytes(source)
+            self.assertEqual(out, result)
+
+    def test_decode_bytes_padding(self):
+        for source, result in self.decode_padding_bytes:
+            out = h64.decode_bytes(source)
+            self.assertEqual(out, result)
+
+    #=========================================================
+    #test transposed encode/decode
+    #=========================================================
+    encode_transposed = [
+        ("\x33\x22\x11", "\x11\x22\x33",[2,1,0]),
+        ("\x22\x33\x11", "\x11\x22\x33",[1,2,0]),
+    ]
+
+    encode_transposed_dups = [
+        ("\x11\x11\x22", "\x11\x22\x33",[0,0,1]),
+    ]
+
+    def test_encode_transposed_bytes(self):
+        for result, input, offsets in self.encode_transposed + self.encode_transposed_dups:
+            tmp = h64.encode_transposed_bytes(input, offsets)
+            out = h64.decode_bytes(tmp)
+            self.assertEqual(out, result)
+
+    def test_decode_transposed_bytes(self):
+        for input, result, offsets in self.encode_transposed:
+            tmp = h64.encode_bytes(input)
+            out = h64.decode_transposed_bytes(tmp, offsets)
+            self.assertEqual(out, result)
+
+    def test_decode_transposed_bytes_bad(self):
+        for input, _, offsets in self.encode_transposed_dups:
+            tmp = h64.encode_bytes(input)
+            self.assertRaises(TypeError, h64.decode_transposed_bytes, tmp, offsets)
+
+    #=========================================================
     #TODO: test other h64 methods
+    #=========================================================
 
 #=========================================================
 #test md4
diff --git a/passlib/utils/h64.py b/passlib/utils/h64.py
index 90e14c2..946b63d 100644
--- a/passlib/utils/h64.py
+++ b/passlib/utils/h64.py
@@ -3,6 +3,7 @@
 #imports
 #=================================================================================
 #core
+from cStringIO import StringIO
 import logging; log = logging.getLogger(__name__)
 #site
 #pkg
@@ -10,20 +11,19 @@ import logging; log = logging.getLogger(__name__)
 __all__ = [
     "CHARS",
 
-                    "encode_bytes",
-                    "encode_3_offsets",
-                    "encode_2_offsets",
-                    "encode_1_offset",
+    "decode_bytes",                "encode_bytes",
+    "decode_transposed_bytes",     "encode_transposed_bytes",
 
     "decode_int6",  "encode_int6",
     "decode_int12", "encode_int12"
+    "decode_int18", "encode_int18"
     "decode_int24", "encode_int24",
     "decode_int64", "encode_int64",
-    "decode_int",
+    "decode_int",   "encode_int",
 ]
 
 #=================================================================================
-#6 bit value <-> char mapping
+#6 bit value <-> char mapping, and other internal helpers
 #=================================================================================
 CHARS = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
 
@@ -34,60 +34,86 @@ encode_6bit = CHARS.__getitem__ # int -> char
 _CHARIDX = dict( (c,i) for i,c in enumerate(CHARS))
 decode_6bit = _CHARIDX.__getitem__ # char -> int
 
+_sjoin = "".join
+
+try:
+    _bjoin = bytes().join
+except NameError:
+    _bjoin = _sjoin
+
 #=================================================================================
 #encode offsets from buffer - used by md5_crypt, sha_crypt, et al
 #=================================================================================
-def encode_3_offsets(buffer, o1, o2, o3):
-    "do hash64 encode of three bytes at specified offsets in buffer; returns 4 chars"
-    #how 4 char output corresponds to 3 byte input:
-    #
-    #1st character: the six low bits of the first byte (0x3F)
-    #
-    #2nd character: four low bits from the second byte (0x0F) shift left 2
-    #               the two high bits of the first byte (0xC0) shift right 6
-    #
-    #3rd character: the two low bits from the third byte (0x03) shift left 4
-    #               the four high bits from the second byte (0xF0) shift right 4
-    #
-    #4th character: the six high bits from the third byte (0xFC) shift right 2
-    v1 = ord(buffer[o1])
-    v2 = ord(buffer[o2])
-    v3 = ord(buffer[o3])
-    return  encode_6bit(v1&0x3F) + \
-            encode_6bit(((v2&0x0F)<<2) + (v1>>6)) + \
-            encode_6bit(((v3&0x03)<<4) + (v2>>4)) + \
-            encode_6bit(v3>>2)
-
-def encode_2_offsets(buffer, o1, o2):
-    "do hash64 encode of two bytes at specified offsets in buffer; 2 missing msg set null; returns 3 chars"
-    v1 = ord(buffer[o1])
-    v2 = ord(buffer[o2])
-    return  encode_6bit(v1&0x3F) + \
-            encode_6bit(((v2&0x0F)<<2) + (v1>>6)) + \
-            encode_6bit((v2>>4))
-
-def encode_1_offset(buffer, o1):
-    "do hash64 encode of single byte at specified offset in buffer; 4 missing msb set null; returns 2 chars"
-    v1 = ord(buffer[o1])
-    return encode_6bit(v1&0x3F) + encode_6bit(v1>>6)
 
 def encode_bytes(source):
     "encode byte string to h64 format"
     #FIXME: do something much more efficient here.
-    out = ''
+    # can't quite just use base64 and then translate chars,
+    # since this scheme is little-endian.
+    out = StringIO()
+    write = out.write
     end = len(source)
+    tail = end % 3
+    end -= tail
     idx = 0
-    while idx <= end-3:
-        out += encode_3_offsets(source, idx, idx+1, idx+2)
+    while idx < end:
+        v1 = ord(source[idx])
+        v2 = ord(source[idx+1])
+        v3 = ord(source[idx+2])
+        write(encode_int24(v1 + (v2<<8) + (v3<<16)))
         idx += 3
-    if end % 3 == 1:
-        out += encode_1_offset(source, idx)
-        idx += 1
-    elif end % 3 == 2:
-        out += encode_2_offset(source, idx, idx+1)
-        idx += 2
-    assert idx == end
-    return out
+    if tail:
+        v1 = ord(source[idx])
+        if tail == 1:
+            #NOTE: 4 msb of int are always 0
+            write(encode_int12(v1))
+        else:
+            #NOTE: 2 msb of int are always 0
+            v2 = ord(source[idx+1])
+            write(encode_int18(v1 + (v2<<8)))
+    return out.getvalue()
+
+def decode_bytes(source):
+    "decode h64 format into byte string"
+    out = StringIO()
+    write = out.write
+    end = len(source)
+    tail = end % 4
+    if tail == 1:
+        #only 6 bits left, can't encode a whole byte!
+        raise ValueError, "input string length cannot be == 1 mod 4"
+    end -= tail
+    idx = 0
+    while idx < end:
+        v = decode_int24(source[idx:idx+4])
+        write(chr(v&0xff) + chr((v>>8)&0xff) + chr(v>>16))
+        idx += 4
+    if tail:
+        if tail == 2:
+            #NOTE: 2 msb of int are ignored (should be 0)
+            v = decode_int12(source[idx:idx+2])
+            write(chr(v&0xff))
+        else:
+            #NOTE: 4 msb of int are ignored (should be 0)
+            v = decode_int18(source[idx:idx+3])
+            write(chr(v&0xff) + chr((v>>8)&0xff))
+    return out.getvalue()
+
+def encode_transposed_bytes(source, offsets):
+    "encode byte string to h64 format, using offset list to transpose elements"
+    #XXX: could make this a dup of encode_bytes(), which directly accesses source[offsets[idx]],
+    # but speed isn't *that* critical for this function
+    tmp = _bjoin(source[off] for off in offsets)
+    return encode_bytes(tmp)
+
+def decode_transposed_bytes(source, offsets):
+    "decode h64 format into byte string, then undoing specified transposition; inverse of :func:`encode_transposed_bytes`"
+    #NOTE: if transposition does not use all bytes of source, original can't be recovered
+    tmp = decode_bytes(source)
+    buf = [None] * len(offsets)
+    for off, char in zip(offsets, tmp):
+        buf[off] = char
+    return _bjoin(buf)
 
 #=================================================================================
 # int <-> b64 string, used by des_crypt, ext_des_crypt
@@ -115,14 +141,31 @@ def encode_int12(value):
     return  encode_6bit(value & 0x3f) + encode_6bit((value>>6) & 0x3f)
 
 #---------------------------------------------------------------------
+def decode_int18(value):
+    "decode 3 chars of hash-64 format, returning 18-bit integer"
+    return (
+        decode_6bit(value[0]) +
+        (decode_6bit(value[1])<<6) +
+        (decode_6bit(value[2])<<12)
+        )
+
+def encode_int18(value):
+    "encode 18-bit integer into 3 chars of hash-64 format"
+    return (
+        encode_6bit(value & 0x3f) +
+        encode_6bit((value>>6) & 0x3f) +
+        encode_6bit((value>>12) & 0x3f)
+        )
+
+#---------------------------------------------------------------------
 
 def decode_int24(value):
     "decode 4 chars of hash-64 format, returning 24-bit integer"
     try:
         return  decode_6bit(value[0]) +\
                 (decode_6bit(value[1])<<6)+\
-                (decode_6bit(value[3])<<18)+\
-                (decode_6bit(value[2])<<12)
+                (decode_6bit(value[2])<<12)+\
+                (decode_6bit(value[3])<<18)
     except KeyError:
         raise ValueError, "invalid character"
 
@@ -135,36 +178,34 @@ def encode_int24(value):
 
 #---------------------------------------------------------------------
 
-_RR9_1 = range(9,-1,-1)
-
 def decode_int64(value):
     "decode 64-bit integer from 11 chars of hash-64 format"
     return decode_int(value)
 
 def encode_int64(value):
     "encode 64-bit integer to hash-64 format, returning 11 chars"
-    out = [None] * 10 + [ encode_6bit((value<<2)&0x3f) ]
-    value >>= 4
-    for i in _RR9_1:
-        out[i] = encode_6bit(value&0x3f)
-        value >>= 6
-    return "".join(out)
+    return encode_int(value)
 
 #---------------------------------------------------------------------
 
-def decode_int(value):
+def decode_int(source):
     "decode hash-64 format used by crypt into integer"
     #FORMAT: little-endian, each char contributes 6 bits,
     # char value = index in H64_CHARS string
     try:
         out = 0
-        for c in reversed(value):
-                out = (out<<6) + b64_decode_6bit(c)
+        for c in reversed(source):
+                out = (out<<6) + decode_6bit(c)
         return out
     except KeyError:
         raise ValueError, "invalid character in string"
 
-## def encode_int(value):
+def encode_int(value, count):
+    "encode integer into hash-64 format"
+    return _sjoin(
+        encode_6bit((value>>off) & 0x3f)
+        for off in xrange(0, 6*count, 6)
+    )
 
 #=================================================================================
 #eof