[catapult] - Copy Telemetry's gsutilz over to third_party.

third_party/gsutil/third_party/crcmod_osx/crcmod/crcmod.py

Index: third_party/gsutil/third_party/crcmod_osx/crcmod/crcmod.py
diff --git a/third_party/gsutil/third_party/crcmod_osx/crcmod/crcmod.py b/third_party/gsutil/third_party/crcmod_osx/crcmod/crcmod.py
new file mode 100644
index 0000000000000000000000000000000000000000..b1e878ff994fdebbabda9ffe2c83777154cd23ae
--- /dev/null
+++ b/third_party/gsutil/third_party/crcmod_osx/crcmod/crcmod.py
@@ -0,0 +1,472 @@
+#-----------------------------------------------------------------------------
+# Copyright (c) 2010  Raymond L. Buvel
+# Copyright (c) 2010  Craig McQueen
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+# 
+# The above copyright notice and this permission notice shall be included in
+# all copies or substantial portions of the Software.
+# 
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+#-----------------------------------------------------------------------------
+'''crcmod is a Python module for gererating objects that compute the Cyclic
+Redundancy Check.  Any 8, 16, 24, 32, or 64 bit polynomial can be used.  
+
+The following are the public components of this module.
+
+Crc -- a class that creates instances providing the same interface as the
+md5 and sha modules in the Python standard library.  These instances also
+provide a method for generating a C/C++ function to compute the CRC.
+
+mkCrcFun -- create a Python function to compute the CRC using the specified
+polynomial and initial value.  This provides a much simpler interface if
+all you need is a function for CRC calculation.
+'''
+
+__all__ = '''mkCrcFun Crc
+'''.split()
+
+# Select the appropriate set of low-level CRC functions for this installation.
+# If the extension module was not built, drop back to the Python implementation
+# even though it is significantly slower.
+try:
+    import _crcfunext as _crcfun
+    _usingExtension = True
+except ImportError:
+    import _crcfunpy as _crcfun
+    _usingExtension = False
+
+import sys, struct
+
+#-----------------------------------------------------------------------------
+class Crc:
+    '''Compute a Cyclic Redundancy Check (CRC) using the specified polynomial.
+
+    Instances of this class have the same interface as the md5 and sha modules
+    in the Python standard library.  See the documentation for these modules
+    for examples of how to use a Crc instance.
+
+    The string representation of a Crc instance identifies the polynomial,
+    initial value, XOR out value, and the current CRC value.  The print
+    statement can be used to output this information.
+
+    If you need to generate a C/C++ function for use in another application,
+    use the generateCode method.  If you need to generate code for another
+    language, subclass Crc and override the generateCode method.
+
+    The following are the parameters supplied to the constructor.
+
+    poly -- The generator polynomial to use in calculating the CRC.  The value
+    is specified as a Python integer or long integer.  The bits in this integer
+    are the coefficients of the polynomial.  The only polynomials allowed are
+    those that generate 8, 16, 24, 32, or 64 bit CRCs.
+
+    initCrc -- Initial value used to start the CRC calculation.  This initial
+    value should be the initial shift register value XORed with the final XOR
+    value.  That is equivalent to the CRC result the algorithm should return for
+    a zero-length string.  Defaults to all bits set because that starting value
+    will take leading zero bytes into account.  Starting with zero will ignore
+    all leading zero bytes.
+
+    rev -- A flag that selects a bit reversed algorithm when True.  Defaults to
+    True because the bit reversed algorithms are more efficient.
+
+    xorOut -- Final value to XOR with the calculated CRC value.  Used by some
+    CRC algorithms.  Defaults to zero.
+    '''
+    def __init__(self, poly, initCrc=~0L, rev=True, xorOut=0, initialize=True):
+        if not initialize:
+            # Don't want to perform the initialization when using new or copy
+            # to create a new instance.
+            return
+
+        (sizeBits, initCrc, xorOut) = _verifyParams(poly, initCrc, xorOut)
+        self.digest_size = sizeBits//8
+        self.initCrc = initCrc
+        self.xorOut = xorOut
+
+        self.poly = poly
+        self.reverse = rev
+
+        (crcfun, table) = _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut)
+        self._crc = crcfun
+        self.table = table
+
+        self.crcValue = self.initCrc
+
+    def __str__(self):
+        lst = []
+        lst.append('poly = 0x%X' % self.poly)
+        lst.append('reverse = %s' % self.reverse)
+        fmt = '0x%%0%dX' % (self.digest_size*2)
+        lst.append('initCrc  = %s' % (fmt % self.initCrc))
+        lst.append('xorOut   = %s' % (fmt % self.xorOut))
+        lst.append('crcValue = %s' % (fmt % self.crcValue))
+        return '\n'.join(lst)
+
+    def new(self, arg=None):
+        '''Create a new instance of the Crc class initialized to the same
+        values as the original instance.  The current CRC is set to the initial
+        value.  If a string is provided in the optional arg parameter, it is
+        passed to the update method.
+        '''
+        n = Crc(poly=None, initialize=False)
+        n._crc = self._crc
+        n.digest_size = self.digest_size
+        n.initCrc = self.initCrc
+        n.xorOut = self.xorOut
+        n.table = self.table
+        n.crcValue = self.initCrc
+        n.reverse = self.reverse
+        n.poly = self.poly
+        if arg is not None:
+            n.update(arg)
+        return n
+
+    def copy(self):
+        '''Create a new instance of the Crc class initialized to the same
+        values as the original instance.  The current CRC is set to the current
+        value.  This allows multiple CRC calculations using a common initial
+        string.
+        '''
+        c = self.new()
+        c.crcValue = self.crcValue
+        return c
+
+    def update(self, data):
+        '''Update the current CRC value using the string specified as the data
+        parameter.
+        '''
+        self.crcValue = self._crc(data, self.crcValue)
+
+    def digest(self):
+        '''Return the current CRC value as a string of bytes.  The length of
+        this string is specified in the digest_size attribute.
+        '''
+        n = self.digest_size
+        crc = self.crcValue
+        lst = []
+        while n > 0:
+            lst.append(chr(crc & 0xFF))
+            crc = crc >> 8
+            n -= 1
+        lst.reverse()
+        return ''.join(lst)
+
+    def hexdigest(self):
+        '''Return the current CRC value as a string of hex digits.  The length
+        of this string is twice the digest_size attribute.
+        '''
+        n = self.digest_size
+        crc = self.crcValue
+        lst = []
+        while n > 0:
+            lst.append('%02X' % (crc & 0xFF))
+            crc = crc >> 8
+            n -= 1
+        lst.reverse()
+        return ''.join(lst)
+
+    def generateCode(self, functionName, out, dataType=None, crcType=None):
+        '''Generate a C/C++ function.
+
+        functionName -- String specifying the name of the function.
+
+        out -- An open file-like object with a write method.  This specifies
+        where the generated code is written.
+
+        dataType -- An optional parameter specifying the data type of the input
+        data to the function.  Defaults to UINT8.
+
+        crcType -- An optional parameter specifying the data type of the CRC
+        value.  Defaults to one of UINT8, UINT16, UINT32, or UINT64 depending
+        on the size of the CRC value.
+        '''
+        if dataType is None:
+            dataType = 'UINT8'
+
+        if crcType is None:
+            size = 8*self.digest_size
+            if size == 24:
+                size = 32
+            crcType = 'UINT%d' % size
+
+        if self.digest_size == 1:
+            # Both 8-bit CRC algorithms are the same
+            crcAlgor = 'table[*data ^ (%s)crc]'
+        elif self.reverse:
+            # The bit reverse algorithms are all the same except for the data
+            # type of the crc variable which is specified elsewhere.
+            crcAlgor = 'table[*data ^ (%s)crc] ^ (crc >> 8)'
+        else:
+            # The forward CRC algorithms larger than 8 bits have an extra shift
+            # operation to get the high byte.
+            shift = 8*(self.digest_size - 1)
+            crcAlgor = 'table[*data ^ (%%s)(crc >> %d)] ^ (crc << 8)' % shift
+
+        fmt = '0x%%0%dX' % (2*self.digest_size)
+        if self.digest_size <= 4:
+            fmt = fmt + 'U,'
+        else:
+            # Need the long long type identifier to keep gcc from complaining.
+            fmt = fmt + 'ULL,'
+
+        # Select the number of entries per row in the output code.
+        n = {1:8, 2:8, 3:4, 4:4, 8:2}[self.digest_size]
+
+        lst = []
+        for i, val in enumerate(self.table):
+            if (i % n) == 0:
+                lst.append('\n    ')
+            lst.append(fmt % val)
+
+        poly = 'polynomial: 0x%X' % self.poly
+        if self.reverse:
+            poly = poly + ', bit reverse algorithm'
+
+        if self.xorOut:
+            # Need to remove the comma from the format.
+            preCondition = '\n    crc = crc ^ %s;' % (fmt[:-1] % self.xorOut)
+            postCondition = preCondition
+        else:
+            preCondition = ''
+            postCondition = ''
+
+        if self.digest_size == 3:
+            # The 24-bit CRC needs to be conditioned so that only 24-bits are
+            # used from the 32-bit variable.
+            if self.reverse:
+                preCondition += '\n    crc = crc & 0xFFFFFFU;'
+            else:
+                postCondition += '\n    crc = crc & 0xFFFFFFU;'
+                
+
+        parms = {
+            'dataType' : dataType,
+            'crcType' : crcType,
+            'name' : functionName,
+            'crcAlgor' : crcAlgor % dataType,
+            'crcTable' : ''.join(lst),
+            'poly' : poly,
+            'preCondition' : preCondition,
+            'postCondition' : postCondition,
+        }
+        out.write(_codeTemplate % parms) 
+
+#-----------------------------------------------------------------------------
+def mkCrcFun(poly, initCrc=~0L, rev=True, xorOut=0):
+    '''Return a function that computes the CRC using the specified polynomial.
+
+    poly -- integer representation of the generator polynomial
+    initCrc -- default initial CRC value
+    rev -- when true, indicates that the data is processed bit reversed.
+    xorOut -- the final XOR value
+
+    The returned function has the following user interface
+    def crcfun(data, crc=initCrc):
+    '''
+
+    # First we must verify the params
+    (sizeBits, initCrc, xorOut) = _verifyParams(poly, initCrc, xorOut)
+    # Make the function (and table), return the function
+    return _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut)[0]
+
+#-----------------------------------------------------------------------------
+# Naming convention:
+# All function names ending with r are bit reverse variants of the ones
+# without the r.
+
+#-----------------------------------------------------------------------------
+# Check the polynomial to make sure that it is acceptable and return the number
+# of bits in the CRC.
+
+def _verifyPoly(poly):
+    msg = 'The degree of the polynomial must be 8, 16, 24, 32 or 64'
+    poly = long(poly) # Use a common representation for all operations
+    for n in (8,16,24,32,64):
+        low = 1L<<n
+        high = low*2
+        if low <= poly < high:
+            return n
+    raise ValueError(msg)
+
+#-----------------------------------------------------------------------------
+# Bit reverse the input value.
+
+def _bitrev(x, n):
+    x = long(x)
+    y = 0L
+    for i in xrange(n):
+        y = (y << 1) | (x & 1L)
+        x = x >> 1
+    if ((1L<<n)-1) <= sys.maxint:
+        return int(y)
+    return y
+
+#-----------------------------------------------------------------------------
+# The following functions compute the CRC for a single byte.  These are used
+# to build up the tables needed in the CRC algorithm.  Assumes the high order
+# bit of the polynomial has been stripped off.
+
+def _bytecrc(crc, poly, n):
+    crc = long(crc)
+    poly = long(poly)
+    mask = 1L<<(n-1)
+    for i in xrange(8):
+        if crc & mask:
+            crc = (crc << 1) ^ poly
+        else:
+            crc = crc << 1
+    mask = (1L<<n) - 1
+    crc = crc & mask
+    if mask <= sys.maxint:
+        return int(crc)
+    return crc
+
+def _bytecrc_r(crc, poly, n):
+    crc = long(crc)
+    poly = long(poly)
+    for i in xrange(8):
+        if crc & 1L:
+            crc = (crc >> 1) ^ poly
+        else:
+            crc = crc >> 1
+    mask = (1L<<n) - 1
+    crc = crc & mask
+    if mask <= sys.maxint:
+        return int(crc)
+    return crc
+
+#-----------------------------------------------------------------------------
+# The following functions compute the table needed to compute the CRC.  The
+# table is returned as a list.  Note that the array module does not support
+# 64-bit integers on a 32-bit architecture as of Python 2.3.
+#
+# These routines assume that the polynomial and the number of bits in the CRC
+# have been checked for validity by the caller.
+
+def _mkTable(poly, n):
+    mask = (1L<<n) - 1
+    poly = long(poly) & mask
+    table = [_bytecrc(long(i)<<(n-8),poly,n) for i in xrange(256)]
+    return table
+
+def _mkTable_r(poly, n):
+    mask = (1L<<n) - 1
+    poly = _bitrev(long(poly) & mask, n)
+    table = [_bytecrc_r(long(i),poly,n) for i in xrange(256)]
+    return table
+
+#-----------------------------------------------------------------------------
+# Map the CRC size onto the functions that handle these sizes.
+
+_sizeMap = {
+     8 : [_crcfun._crc8, _crcfun._crc8r],
+    16 : [_crcfun._crc16, _crcfun._crc16r],
+    24 : [_crcfun._crc24, _crcfun._crc24r],
+    32 : [_crcfun._crc32, _crcfun._crc32r],
+    64 : [_crcfun._crc64, _crcfun._crc64r],
+}
+
+#-----------------------------------------------------------------------------
+# Build a mapping of size to struct module type code.  This table is
+# constructed dynamically so that it has the best chance of picking the best
+# code to use for the platform we are running on.  This should properly adapt
+# to 32 and 64 bit machines.
+
+_sizeToTypeCode = {}
+
+for typeCode in 'B H I L Q'.split():
+    size = {1:8, 2:16, 4:32, 8:64}.get(struct.calcsize(typeCode),None)
+    if size is not None and size not in _sizeToTypeCode:
+        _sizeToTypeCode[size] = '256%s' % typeCode
+
+_sizeToTypeCode[24] = _sizeToTypeCode[32]
+
+del typeCode, size
+
+#-----------------------------------------------------------------------------
+# The following function validates the parameters of the CRC, namely,
+# poly, and initial/final XOR values.
+# It returns the size of the CRC (in bits), and "sanitized" initial/final XOR values.
+
+def _verifyParams(poly, initCrc, xorOut):
+    sizeBits = _verifyPoly(poly)
+
+    mask = (1L<<sizeBits) - 1
+
+    # Adjust the initial CRC to the correct data type (unsigned value).
+    initCrc = long(initCrc) & mask
+    if mask <= sys.maxint:
+        initCrc = int(initCrc)
+
+    # Similar for XOR-out value.
+    xorOut = long(xorOut) & mask
+    if mask <= sys.maxint:
+        xorOut = int(xorOut)
+
+    return (sizeBits, initCrc, xorOut)
+
+#-----------------------------------------------------------------------------
+# The following function returns a Python function to compute the CRC.
+#
+# It must be passed parameters that are already verified & sanitized by
+# _verifyParams().
+#
+# The returned function calls a low level function that is written in C if the
+# extension module could be loaded.  Otherwise, a Python implementation is
+# used.
+#
+# In addition to this function, a list containing the CRC table is returned.
+
+def _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut):
+    if rev:
+        tableList = _mkTable_r(poly, sizeBits)
+        _fun = _sizeMap[sizeBits][1]
+    else:
+        tableList = _mkTable(poly, sizeBits)
+        _fun = _sizeMap[sizeBits][0]
+
+    _table = tableList
+    if _usingExtension:
+        _table = struct.pack(_sizeToTypeCode[sizeBits], *tableList)
+
+    if xorOut == 0:
+        def crcfun(data, crc=initCrc, table=_table, fun=_fun):
+            return fun(data, crc, table)
+    else:
+        def crcfun(data, crc=initCrc, table=_table, fun=_fun):
+            return xorOut ^ fun(data, xorOut ^ crc, table)
+
+    return crcfun, tableList
+
+#-----------------------------------------------------------------------------
+_codeTemplate = '''// Automatically generated CRC function
+// %(poly)s
+%(crcType)s
+%(name)s(%(dataType)s *data, int len, %(crcType)s crc)
+{
+    static const %(crcType)s table[256] = {%(crcTable)s
+    };
+    %(preCondition)s
+    while (len > 0)
+    {
+        crc = %(crcAlgor)s;
+        data++;
+        len--;
+    }%(postCondition)s
+    return crc;
+}
+'''
+