Roll version of gsutil to 4.15.

third_party/gsutil/gslib/hashing_helper.py

 # -*- coding: utf-8 -*-
 # Copyright 2014 Google Inc. All Rights Reserved.
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
 # You may obtain a copy of the License at
 #
 #     http://www.apache.org/licenses/LICENSE-2.0
 #
 # Unless required by applicable law or agreed to in writing, software
@@ skipping 61 matching lines @@
 file.
 """
 
 
 # Configuration values for hashing.
 CHECK_HASH_IF_FAST_ELSE_FAIL = 'if_fast_else_fail'
 CHECK_HASH_IF_FAST_ELSE_SKIP = 'if_fast_else_skip'
 CHECK_HASH_ALWAYS = 'always'
 CHECK_HASH_NEVER = 'never'
 
+# Table storing polynomial values of x^(2^k) mod CASTAGNOLI_POLY for all k < 31,
+# where x^(2^k) and CASTAGNOLI_POLY are both considered polynomials. This is
+# sufficient since x^(2^31) mod CASTAGNOLI_POLY = x.
+X_POW_2K_TABLE = [2, 4, 16, 256, 65536, 517762881, 984302966,
+                  408362264, 1503875210, 2862076957, 3884826397, 1324787473,
+                  621200174, 1758783527, 1416537776, 1180494764, 648569364,
+                  2521473789, 994858823, 1728245375, 3498467999, 4059169852,
+                  3345064394, 2828422810, 2429203150, 3336788029, 860151998,
+                  2102628683, 1033187991, 4243778976, 1123580069]
+# Castagnoli polynomial and its degree.
+CASTAGNOLI_POLY = 4812730177
+DEGREE = 32
+
+
+def ConcatCrc32c(crc_a, crc_b, num_bytes_in_b):
+  """Computes CRC32C for concat(A, B) given crc(A), crc(B) and len(B).
+
+  An explanation of the algorithm can be found at
+  crcutil.googlecode.com/files/crc-doc.1.0.pdf.
+
+  Args:
+    crc_a: A 32-bit integer representing crc(A) with least-significant
+           coefficient first.
+    crc_b: Same as crc_a.
+    num_bytes_in_b: Length of B in bytes.
+
+  Returns:
+    CRC32C for concat(A, B)
+  """
+  if not num_bytes_in_b:
+    return crc_a
+
+  return _ExtendByZeros(crc_a, 8 * num_bytes_in_b) ^ crc_b
+
+
+def _CrcMultiply(p, q):
+  """Multiplies two polynomials together modulo CASTAGNOLI_POLY.
+
+  Args:
+    p: The first polynomial.
+    q: The second polynomial.
+
+  Returns:
+    Result of the multiplication.
+  """
+
+  result = 0
+  top_bit = 1 << DEGREE
+  for _ in range(DEGREE):
+    if p & 1:
+      result ^= q
+    q <<= 1
+    if q & top_bit:
+      q ^= CASTAGNOLI_POLY
+    p >>= 1
+  return result
+
+
+def _ExtendByZeros(crc, num_bits):
+  """Given crc representing polynomial P(x), compute P(x)*x^num_bits.
+
+  Args:
+    crc: crc respresenting polynomial P(x).
+    num_bits: number of bits in crc.
+
+  Returns:
+    P(x)*x^num_bits
+  """
+  def _ReverseBits32(crc):
+    return int('{0:032b}'.format(crc, width=32)[::-1], 2)
+  crc = _ReverseBits32(crc)
+  i = 0
+
+  while num_bits != 0:
+    if num_bits & 1:
+      crc = _CrcMultiply(crc, X_POW_2K_TABLE[i % len(X_POW_2K_TABLE)])
+    i += 1
+    num_bits >>= 1
+  crc = _ReverseBits32(crc)
+  return crc
+
 
 def _CalculateHashFromContents(fp, hash_alg):
   """Calculates a base64 digest of the contents of a seekable stream.
 
   This function resets the file pointer to position 0.
 
   Args:
     fp: An already-open file object.
     hash_alg: Instance of hashing class initialized to start state.
 
@@ skipping 113 matching lines @@
   Returns:
     dict of (algorithm_name: hash_algorithm)
   """
   check_hashes_config = config.get(
       'GSUtil', 'check_hashes', CHECK_HASH_IF_FAST_ELSE_FAIL)
   if check_hashes_config == 'never':
     return {}
   return {'md5': md5}
 
 
-def GetDownloadHashAlgs(logger, src_has_md5=False, src_has_crc32c=False):
+def GetDownloadHashAlgs(logger, consider_md5=False, consider_crc32c=False):
   """Returns a dict of hash algorithms for validating an object.
 
   Args:
     logger: logging.Logger for outputting log messages.
-    src_has_md5: If True, source object has an md5 hash.
-    src_has_crc32c: If True, source object has a crc32c hash.
+    consider_md5: If True, consider using a md5 hash.
+    consider_crc32c: If True, consider using a crc32c hash.
 
   Returns:
     Dict of (string, hash algorithm).
 
   Raises:
     CommandException if hash algorithms satisfying the boto config file
     cannot be returned.
   """
   check_hashes_config = config.get(
       'GSUtil', 'check_hashes', CHECK_HASH_IF_FAST_ELSE_FAIL)
   if check_hashes_config == CHECK_HASH_NEVER:
     return {}
 
   hash_algs = {}
-  if src_has_md5:
+  if consider_md5:
     hash_algs['md5'] = md5
-  elif src_has_crc32c:
+  elif consider_crc32c:
     # If the cloud provider supplies a CRC, we'll compute a checksum to
     # validate if we're using a native crcmod installation and MD5 isn't
     # offered as an alternative.
     if UsingCrcmodExtension(crcmod):
       hash_algs['crc32c'] = lambda: crcmod.predefined.Crc('crc-32c')
     elif not hash_algs:
       if check_hashes_config == CHECK_HASH_IF_FAST_ELSE_FAIL:
         raise CommandException(_SLOW_CRC_EXCEPTION_TEXT)
       elif check_hashes_config == CHECK_HASH_IF_FAST_ELSE_SKIP:
         logger.warn(_NO_HASH_CHECK_WARNING)
@@ skipping 160 matching lines @@
     self._digesters_previous_mark = self._digesters_current_mark
     bytes_remaining = bytes_to_read
     bytes_this_round = min(bytes_remaining, TRANSFER_BUFFER_SIZE)
     while bytes_this_round:
       data = self._orig_fp.read(bytes_this_round)
       bytes_remaining -= bytes_this_round
       for alg in self._digesters:
         self._digesters[alg].update(data)
       bytes_this_round = min(bytes_remaining, TRANSFER_BUFFER_SIZE)
     self._digesters_current_mark += bytes_to_read