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

third_party/gsutil/third_party/crcmod/python2/crcmod/test.py

Index: third_party/gsutil/third_party/crcmod/python2/crcmod/test.py
diff --git a/third_party/gsutil/third_party/crcmod/python2/crcmod/test.py b/third_party/gsutil/third_party/crcmod/python2/crcmod/test.py
new file mode 100644
index 0000000000000000000000000000000000000000..44af45d3aed47ea00755053477718ed9cbe51d49
--- /dev/null
+++ b/third_party/gsutil/third_party/crcmod/python2/crcmod/test.py
@@ -0,0 +1,500 @@
+#-----------------------------------------------------------------------------
+# 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.
+#-----------------------------------------------------------------------------
+'''Unit tests for crcmod functionality'''
+
+
+import unittest
+
+import binascii
+
+from crcmod import mkCrcFun, Crc
+try:
+    from crcmod.crcmod import _usingExtension
+    from crcmod.predefined import PredefinedCrc
+    from crcmod.predefined import mkPredefinedCrcFun
+    from crcmod.predefined import _crc_definitions as _predefined_crc_definitions
+except ImportError:
+    from crcmod import _usingExtension
+    from predefined import PredefinedCrc
+    from predefined import mkPredefinedCrcFun
+    from predefined import _crc_definitions as _predefined_crc_definitions
+
+
+#-----------------------------------------------------------------------------
+# This polynomial was chosen because it is the product of two irreducible
+# polynomials.
+# g8 = (x^7+x+1)*(x+1)
+g8 = 0x185
+
+#-----------------------------------------------------------------------------
+# The following reproduces all of the entries in the Numerical Recipes table.
+# This is the standard CCITT polynomial.
+g16 = 0x11021
+
+#-----------------------------------------------------------------------------
+g24 = 0x15D6DCB
+
+#-----------------------------------------------------------------------------
+# This is the standard AUTODIN-II polynomial which appears to be used in a
+# wide variety of standards and applications.
+g32 = 0x104C11DB7
+
+
+#-----------------------------------------------------------------------------
+# I was able to locate a couple of 64-bit polynomials on the web.  To make it
+# easier to input the representation, define a function that builds a
+# polynomial from a list of the bits that need to be turned on.
+
+def polyFromBits(bits):
+    p = 0L
+    for n in bits:
+        p = p | (1L << n)
+    return p
+
+# The following is from the paper "An Improved 64-bit Cyclic Redundancy Check
+# for Protein Sequences" by David T. Jones
+
+g64a = polyFromBits([64, 63, 61, 59, 58, 56, 55, 52, 49, 48, 47, 46, 44, 41,
+            37, 36, 34, 32, 31, 28, 26, 23, 22, 19, 16, 13, 12, 10, 9, 6, 4,
+            3, 0])
+
+# The following is from Standard ECMA-182 "Data Interchange on 12,7 mm 48-Track
+# Magnetic Tape Cartridges -DLT1 Format-", December 1992.
+
+g64b = polyFromBits([64, 62, 57, 55, 54, 53, 52, 47, 46, 45, 40, 39, 38, 37,
+            35, 33, 32, 31, 29, 27, 24, 23, 22, 21, 19, 17, 13, 12, 10, 9, 7,
+            4, 1, 0])
+
+#-----------------------------------------------------------------------------
+# This class is used to check the CRC calculations against a direct
+# implementation using polynomial division.
+
+class poly:
+    '''Class implementing polynomials over the field of integers mod 2'''
+    def __init__(self,p):
+        p = long(p)
+        if p < 0: raise ValueError('invalid polynomial')
+        self.p = p
+
+    def __long__(self):
+        return self.p
+
+    def __eq__(self,other):
+        return self.p == other.p
+
+    def __ne__(self,other):
+        return self.p != other.p
+
+    # To allow sorting of polynomials, use their long integer form for
+    # comparison
+    def __cmp__(self,other):
+        return cmp(self.p, other.p)
+
+    def __nonzero__(self):
+        return self.p != 0L
+
+    def __neg__(self):
+        return self # These polynomials are their own inverse under addition
+
+    def __invert__(self):
+        n = max(self.deg() + 1, 1)
+        x = (1L << n) - 1
+        return poly(self.p ^ x)
+
+    def __add__(self,other):
+        return poly(self.p ^ other.p)
+
+    def __sub__(self,other):
+        return poly(self.p ^ other.p)
+
+    def __mul__(self,other):
+        a = self.p
+        b = other.p
+        if a == 0 or b == 0: return poly(0)
+        x = 0L
+        while b:
+            if b&1:
+                x = x ^ a
+            a = a<<1
+            b = b>>1
+        return poly(x)
+
+    def __divmod__(self,other):
+        u = self.p
+        m = self.deg()
+        v = other.p
+        n = other.deg()
+        if v == 0: raise ZeroDivisionError('polynomial division by zero')
+        if n == 0: return (self,poly(0))
+        if m < n: return (poly(0),self)
+        k = m-n
+        a = 1L << m
+        v = v << k
+        q = 0L
+        while k > 0:
+            if a & u:
+                u = u ^ v
+                q = q | 1L
+            q = q << 1
+            a = a >> 1
+            v = v >> 1
+            k -= 1
+        if a & u:
+            u = u ^ v
+            q = q | 1L
+        return (poly(q),poly(u))
+
+    def __div__(self,other):
+        return self.__divmod__(other)[0]
+
+    def __mod__(self,other):
+        return self.__divmod__(other)[1]
+
+    def __repr__(self):
+        return 'poly(0x%XL)' % self.p
+
+    def __str__(self):
+        p = self.p
+        if p == 0: return '0'
+        lst = { 0:[], 1:['1'], 2:['x'], 3:['1','x'] }[p&3]
+        p = p>>2
+        n = 2
+        while p:
+            if p&1: lst.append('x^%d' % n)
+            p = p>>1
+            n += 1
+        lst.reverse()
+        return '+'.join(lst)
+
+    def deg(self):
+        '''return the degree of the polynomial'''
+        a = self.p
+        if a == 0: return -1
+        n = 0
+        while a >= 0x10000L:
+            n += 16
+            a = a >> 16
+        a = int(a)
+        while a > 1:
+            n += 1
+            a = a >> 1
+        return n
+
+#-----------------------------------------------------------------------------
+# The following functions compute the CRC using direct polynomial division.
+# These functions are checked against the result of the table driven
+# algorithms.
+
+g8p = poly(g8)
+x8p = poly(1L<<8)
+def crc8p(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x8p%g8p)
+
+g16p = poly(g16)
+x16p = poly(1L<<16)
+def crc16p(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x16p%g16p)
+
+g24p = poly(g24)
+x24p = poly(1L<<24)
+def crc24p(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x24p%g24p)
+
+g32p = poly(g32)
+x32p = poly(1L<<32)
+def crc32p(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x32p%g32p)
+
+g64ap = poly(g64a)
+x64p = poly(1L<<64)
+def crc64ap(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x64p%g64ap)
+
+g64bp = poly(g64b)
+def crc64bp(d):
+    d = map(ord, d)
+    p = 0L
+    for i in d:
+        p = p*256L + i
+    p = poly(p)
+    return long(p*x64p%g64bp)
+
+
+class KnownAnswerTests(unittest.TestCase):
+    test_messages = [
+        'T',
+        'CatMouse987654321',
+    ]
+
+    known_answers = [
+        [ (g8,0,0),             (0xFE,          0x9D)           ],
+        [ (g8,-1,1),            (0x4F,          0x9B)           ],
+        [ (g8,0,1),             (0xFE,          0x62)           ],
+        [ (g16,0,0),            (0x1A71,        0xE556)         ],
+        [ (g16,-1,1),           (0x1B26,        0xF56E)         ],
+        [ (g16,0,1),            (0x14A1,        0xC28D)         ],
+        [ (g24,0,0),            (0xBCC49D,      0xC4B507)       ],
+        [ (g24,-1,1),           (0x59BD0E,      0x0AAA37)       ],
+        [ (g24,0,1),            (0xD52B0F,      0x1523AB)       ],
+        [ (g32,0,0),            (0x6B93DDDB,    0x12DCA0F4)     ],
+        [ (g32,0xFFFFFFFFL,1),  (0x41FB859FL,   0xF7B400A7L)    ],
+        [ (g32,0,1),            (0x6C0695EDL,   0xC1A40EE5L)    ],
+        [ (g32,0,1,0xFFFFFFFF), (0xBE047A60L,   0x084BFF58L)    ],
+    ]
+
+    def test_known_answers(self):
+        for crcfun_params, v in self.known_answers:
+            crcfun = mkCrcFun(*crcfun_params)
+            self.assertEqual(crcfun('',0), 0, "Wrong answer for CRC parameters %s, input ''" % (crcfun_params,))
+            for i, msg in enumerate(self.test_messages):
+                self.assertEqual(crcfun(msg), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg))
+                self.assertEqual(crcfun(msg[4:], crcfun(msg[:4])), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg))
+                self.assertEqual(crcfun(msg[-1:], crcfun(msg[:-1])), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg))
+
+
+class CompareReferenceCrcTest(unittest.TestCase):
+    test_messages = [
+        '',
+        'T',
+        '123456789',
+        'CatMouse987654321',
+    ]
+
+    test_poly_crcs = [
+        [ (g8,0,0),     crc8p    ],
+        [ (g16,0,0),    crc16p   ],
+        [ (g24,0,0),    crc24p   ],
+        [ (g32,0,0),    crc32p   ],
+        [ (g64a,0,0),   crc64ap  ],
+        [ (g64b,0,0),   crc64bp  ],
+    ]
+
+    @staticmethod
+    def reference_crc32(d, crc=0):
+        """This function modifies the return value of binascii.crc32
+        to be an unsigned 32-bit value. I.e. in the range 0 to 2**32-1."""
+        # Work around the future warning on constants.
+        if crc > 0x7FFFFFFFL:
+            x = int(crc & 0x7FFFFFFFL)
+            crc = x | -2147483648
+        x = binascii.crc32(d,crc)
+        return long(x) & 0xFFFFFFFFL
+
+    def test_compare_crc32(self):
+        """The binascii module has a 32-bit CRC function that is used in a wide range
+        of applications including the checksum used in the ZIP file format.
+        This test compares the CRC-32 implementation of this crcmod module to
+        that of binascii.crc32."""
+        # The following function should produce the same result as
+        # self.reference_crc32 which is derived from binascii.crc32.
+        crc32 = mkCrcFun(g32,0,1,0xFFFFFFFF)
+
+        for msg in self.test_messages:
+            self.assertEqual(crc32(msg), self.reference_crc32(msg))
+
+    def test_compare_poly(self):
+        """Compare various CRCs of this crcmod module to a pure
+        polynomial-based implementation."""
+        for crcfun_params, crc_poly_fun in self.test_poly_crcs:
+            # The following function should produce the same result as
+            # the associated polynomial CRC function.
+            crcfun = mkCrcFun(*crcfun_params)
+
+            for msg in self.test_messages:
+                self.assertEqual(crcfun(msg), crc_poly_fun(msg))
+
+
+class CrcClassTest(unittest.TestCase):
+    """Verify the Crc class"""
+
+    msg = 'CatMouse987654321'
+
+    def test_simple_crc32_class(self):
+        """Verify the CRC class when not using xorOut"""
+        crc = Crc(g32)
+
+        str_rep = \
+'''poly = 0x104C11DB7
+reverse = True
+initCrc  = 0xFFFFFFFF
+xorOut   = 0x00000000
+crcValue = 0xFFFFFFFF'''
+        self.assertEqual(str(crc), str_rep)
+        self.assertEqual(crc.digest(), '\xff\xff\xff\xff')
+        self.assertEqual(crc.hexdigest(), 'FFFFFFFF')
+
+        crc.update(self.msg)
+        self.assertEqual(crc.crcValue, 0xF7B400A7L)
+        self.assertEqual(crc.digest(), '\xf7\xb4\x00\xa7')
+        self.assertEqual(crc.hexdigest(), 'F7B400A7')
+
+        # Verify the .copy() method
+        x = crc.copy()
+        self.assertTrue(x is not crc)
+        str_rep = \
+'''poly = 0x104C11DB7
+reverse = True
+initCrc  = 0xFFFFFFFF
+xorOut   = 0x00000000
+crcValue = 0xF7B400A7'''
+        self.assertEqual(str(crc), str_rep)
+        self.assertEqual(str(x), str_rep)
+
+    def test_full_crc32_class(self):
+        """Verify the CRC class when using xorOut"""
+
+        crc = Crc(g32, initCrc=0, xorOut= ~0L)
+
+        str_rep = \
+'''poly = 0x104C11DB7
+reverse = True
+initCrc  = 0x00000000
+xorOut   = 0xFFFFFFFF
+crcValue = 0x00000000'''
+        self.assertEqual(str(crc), str_rep)
+        self.assertEqual(crc.digest(), '\x00\x00\x00\x00')
+        self.assertEqual(crc.hexdigest(), '00000000')
+
+        crc.update(self.msg)
+        self.assertEqual(crc.crcValue, 0x84BFF58L)
+        self.assertEqual(crc.digest(), '\x08\x4b\xff\x58')
+        self.assertEqual(crc.hexdigest(), '084BFF58')
+
+        # Verify the .copy() method
+        x = crc.copy()
+        self.assertTrue(x is not crc)
+        str_rep = \
+'''poly = 0x104C11DB7
+reverse = True
+initCrc  = 0x00000000
+xorOut   = 0xFFFFFFFF
+crcValue = 0x084BFF58'''
+        self.assertEqual(str(crc), str_rep)
+        self.assertEqual(str(x), str_rep)
+
+        # Verify the .new() method
+        y = crc.new()
+        self.assertTrue(y is not crc)
+        self.assertTrue(y is not x)
+        str_rep = \
+'''poly = 0x104C11DB7
+reverse = True
+initCrc  = 0x00000000
+xorOut   = 0xFFFFFFFF
+crcValue = 0x00000000'''
+        self.assertEqual(str(y), str_rep)
+
+
+class PredefinedCrcTest(unittest.TestCase):
+    """Verify the predefined CRCs"""
+
+    test_messages_for_known_answers = [
+        '',                            # Test cases below depend on this first entry being the empty string. 
+        'T',
+        'CatMouse987654321',
+    ]
+
+    known_answers = [
+        [ 'crc-aug-ccitt',  (0x1D0F,        0xD6ED,        0x5637)         ],
+        [ 'x-25',           (0x0000,        0xE4D9,        0x0A91)         ],
+        [ 'crc-32',         (0x00000000,    0xBE047A60,    0x084BFF58)     ],
+    ]
+
+    def test_known_answers(self):
+        for crcfun_name, v in self.known_answers:
+            crcfun = mkPredefinedCrcFun(crcfun_name)
+            self.assertEqual(crcfun('',0), 0, "Wrong answer for CRC '%s', input ''" % crcfun_name)
+            for i, msg in enumerate(self.test_messages_for_known_answers):
+                self.assertEqual(crcfun(msg), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg))
+                self.assertEqual(crcfun(msg[4:], crcfun(msg[:4])), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg))
+                self.assertEqual(crcfun(msg[-1:], crcfun(msg[:-1])), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg))
+
+    def test_class_with_known_answers(self):
+        for crcfun_name, v in self.known_answers:
+            for i, msg in enumerate(self.test_messages_for_known_answers):
+                crc1 = PredefinedCrc(crcfun_name)
+                crc1.update(msg)
+                self.assertEqual(crc1.crcValue, v[i], "Wrong answer for crc1 %s, input '%s'" % (crcfun_name,msg))
+
+                crc2 = crc1.new()
+                # Check that crc1 maintains its same value, after .new() call.
+                self.assertEqual(crc1.crcValue, v[i], "Wrong state for crc1 %s, input '%s'" % (crcfun_name,msg))
+                # Check that the new class instance created by .new() contains the initialisation value.
+                # This depends on the first string in self.test_messages_for_known_answers being
+                # the empty string.
+                self.assertEqual(crc2.crcValue, v[0], "Wrong state for crc2 %s, input '%s'" % (crcfun_name,msg))
+
+                crc2.update(msg)
+                # Check that crc1 maintains its same value, after crc2 has called .update()
+                self.assertEqual(crc1.crcValue, v[i], "Wrong state for crc1 %s, input '%s'" % (crcfun_name,msg))
+                # Check that crc2 contains the right value after calling .update()
+                self.assertEqual(crc2.crcValue, v[i], "Wrong state for crc2 %s, input '%s'" % (crcfun_name,msg))
+
+    def test_function_predefined_table(self):
+        for table_entry in _predefined_crc_definitions:
+            # Check predefined function
+            crc_func = mkPredefinedCrcFun(table_entry['name'])
+            calc_value = crc_func("123456789")
+            self.assertEqual(calc_value, table_entry['check'], "Wrong answer for CRC '%s'" % table_entry['name'])
+
+    def test_class_predefined_table(self):
+        for table_entry in _predefined_crc_definitions:
+            # Check predefined class
+            crc1 = PredefinedCrc(table_entry['name'])
+            crc1.update("123456789")
+            self.assertEqual(crc1.crcValue, table_entry['check'], "Wrong answer for CRC '%s'" % table_entry['name'])
+
+
+def runtests():
+    print "Using extension:", _usingExtension
+    print
+    unittest.main()
+
+
+if __name__ == '__main__':
+    runtests()