mercurial/pure/base85.py
author Alejandro Santos <alejolp@alejolp.com>
Sun, 05 Jul 2009 11:00:44 +0200
changeset 9029 0001e49f1c11
parent 8632 9e055cfdd620
child 10263 25e572394f5c
permissions -rw-r--r--
compat: use // for integer division
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     1
# base85.py: pure python base85 codec
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     2
#
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     3
# Copyright (C) 2009 Brendan Cully <brendan@kublai.com>
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     4
#
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7881
diff changeset
     5
# This software may be used and distributed according to the terms of the
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7881
diff changeset
     6
# GNU General Public License version 2, incorporated herein by reference.
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     7
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     8
import struct
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
     9
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    10
_b85chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" \
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    11
            "abcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"
7835
2505e9f84153 Optimization of pure.base85.b85encode
Mads Kiilerich <mads@kiilerich.com>
parents: 7701
diff changeset
    12
_b85chars2 = [(a + b) for a in _b85chars for b in _b85chars]
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    13
_b85dec = {}
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    14
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    15
def _mkb85dec():
8632
9e055cfdd620 replace "i in range(len(xs))" with "i, x in enumerate(xs)"
Martin Geisler <mg@lazybytes.net>
parents: 8225
diff changeset
    16
    for i, c in enumerate(_b85chars):
9e055cfdd620 replace "i in range(len(xs))" with "i, x in enumerate(xs)"
Martin Geisler <mg@lazybytes.net>
parents: 8225
diff changeset
    17
        _b85dec[c] = i
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    18
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    19
def b85encode(text, pad=False):
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    20
    """encode text in base85 format"""
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    21
    l = len(text)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    22
    r = l % 4
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    23
    if r:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    24
        text += '\0' * (4 - r)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    25
    longs = len(text) >> 2
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    26
    words = struct.unpack('>%dL' % (longs), text)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    27
9029
0001e49f1c11 compat: use // for integer division
Alejandro Santos <alejolp@alejolp.com>
parents: 8632
diff changeset
    28
    out = ''.join(_b85chars[(word // 52200625) % 85] +
0001e49f1c11 compat: use // for integer division
Alejandro Santos <alejolp@alejolp.com>
parents: 8632
diff changeset
    29
                  _b85chars2[(word // 7225) % 7225] +
7835
2505e9f84153 Optimization of pure.base85.b85encode
Mads Kiilerich <mads@kiilerich.com>
parents: 7701
diff changeset
    30
                  _b85chars2[word % 7225]
2505e9f84153 Optimization of pure.base85.b85encode
Mads Kiilerich <mads@kiilerich.com>
parents: 7701
diff changeset
    31
                  for word in words)
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    32
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    33
    if pad:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    34
        return out
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    35
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    36
    # Trim padding
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    37
    olen = l % 4
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    38
    if olen:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    39
        olen += 1
9029
0001e49f1c11 compat: use // for integer division
Alejandro Santos <alejolp@alejolp.com>
parents: 8632
diff changeset
    40
    olen += l // 4 * 5
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    41
    return out[:olen]
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    42
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    43
def b85decode(text):
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    44
    """decode base85-encoded text"""
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    45
    if not _b85dec:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    46
        _mkb85dec()
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    47
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    48
    l = len(text)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    49
    out = []
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    50
    for i in range(0, len(text), 5):
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    51
        chunk = text[i:i+5]
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    52
        acc = 0
8632
9e055cfdd620 replace "i in range(len(xs))" with "i, x in enumerate(xs)"
Martin Geisler <mg@lazybytes.net>
parents: 8225
diff changeset
    53
        for j, c in enumerate(chunk):
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    54
            try:
8632
9e055cfdd620 replace "i in range(len(xs))" with "i, x in enumerate(xs)"
Martin Geisler <mg@lazybytes.net>
parents: 8225
diff changeset
    55
                acc = acc * 85 + _b85dec[c]
7701
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    56
            except KeyError:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    57
                raise TypeError('Bad base85 character at byte %d' % (i + j))
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    58
        if acc > 4294967295:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    59
            raise OverflowError('Base85 overflow in hunk starting at byte %d' % i)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    60
        out.append(acc)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    61
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    62
    # Pad final chunk if necessary
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    63
    cl = l % 5
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    64
    if cl:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    65
        acc *= 85 ** (5 - cl)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    66
        if cl > 1:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    67
            acc += 0xffffff >> (cl - 2) * 8
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    68
        out[-1] = acc
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    69
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    70
    out = struct.pack('>%dL' % (len(out)), *out)
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    71
    if cl:
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    72
        out = out[:-(5 - cl)]
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    73
4bdead043d8d Pure python base85 fallback
Brendan Cully <brendan@kublai.com>
parents:
diff changeset
    74
    return out