Update brotli to v1.0.0-snapshot.

third_party/brotli/enc/prefix.h

 /* Copyright 2013 Google Inc. All Rights Reserved.
 
    Distributed under MIT license.
    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
 */
 
-// Functions for encoding of integers into prefix codes the amount of extra
-// bits, and the actual values of the extra bits.
+/* Functions for encoding of integers into prefix codes the amount of extra
+   bits, and the actual values of the extra bits. */
 
 #ifndef BROTLI_ENC_PREFIX_H_
 #define BROTLI_ENC_PREFIX_H_
 
+#include "../common/constants.h"
+#include <brotli/port.h>
+#include <brotli/types.h>
 #include "./fast_log.h"
-#include "./types.h"
 
-namespace brotli {
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
 
-static const uint32_t kNumInsertLenPrefixes = 24;
-static const uint32_t kNumCopyLenPrefixes = 24;
-static const uint32_t kNumCommandPrefixes = 704;
-static const uint32_t kNumBlockLenPrefixes = 26;
-static const uint32_t kNumDistanceShortCodes = 16;
-static const uint32_t kNumDistancePrefixes = 520;
-
-// Represents the range of values belonging to a prefix code:
-// [offset, offset + 2^nbits)
-struct PrefixCodeRange {
-  uint32_t offset;
-  uint32_t nbits;
-};
-
-static const PrefixCodeRange kBlockLengthPrefixCode[kNumBlockLenPrefixes] = {
-  {   1,  2}, {    5,  2}, {  9,   2}, {  13,  2},
-  {  17,  3}, {   25,  3}, {  33,  3}, {  41,  3},
-  {  49,  4}, {   65,  4}, {  81,  4}, {  97,  4},
-  { 113,  5}, {  145,  5}, { 177,  5}, { 209,  5},
-  { 241,  6}, {  305,  6}, { 369,  7}, { 497,  8},
-  { 753,  9}, { 1265, 10}, {2289, 11}, {4337, 12},
-  {8433, 13}, {16625, 24}
-};
-
-inline void GetBlockLengthPrefixCode(uint32_t len, uint32_t* code,
-                                     uint32_t* n_extra, uint32_t* extra) {
-  *code = 0;
-  while (*code < 25 && len >= kBlockLengthPrefixCode[*code + 1].offset) {
-    ++(*code);
+/* Here distance_code is an intermediate code, i.e. one of the special codes or
+   the actual distance increased by BROTLI_NUM_DISTANCE_SHORT_CODES - 1. */
+static BROTLI_INLINE void PrefixEncodeCopyDistance(size_t distance_code,
+                                                   size_t num_direct_codes,
+                                                   size_t postfix_bits,
+                                                   uint16_t* code,
+                                                   uint32_t* extra_bits) {
+  if (distance_code < BROTLI_NUM_DISTANCE_SHORT_CODES + num_direct_codes) {
+    *code = (uint16_t)distance_code;
+    *extra_bits = 0;
+    return;
+  } else {
+    size_t dist = ((size_t)1 << (postfix_bits + 2u)) +
+        (distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES - num_direct_codes);
+    size_t bucket = Log2FloorNonZero(dist) - 1;
+    size_t postfix_mask = (1u << postfix_bits) - 1;
+    size_t postfix = dist & postfix_mask;
+    size_t prefix = (dist >> bucket) & 1;
+    size_t offset = (2 + prefix) << bucket;
+    size_t nbits = bucket - postfix_bits;
+    *code = (uint16_t)(
+        (BROTLI_NUM_DISTANCE_SHORT_CODES + num_direct_codes +
+         ((2 * (nbits - 1) + prefix) << postfix_bits) + postfix));
+    *extra_bits = (uint32_t)(
+        (nbits << 24) | ((dist - offset) >> postfix_bits));
   }
-  *n_extra = kBlockLengthPrefixCode[*code].nbits;
-  *extra = len - kBlockLengthPrefixCode[*code].offset;
 }
 
-inline void PrefixEncodeCopyDistance(size_t distance_code,
-                                     size_t num_direct_codes,
-                                     size_t postfix_bits,
-                                     uint16_t* code,
-                                     uint32_t* extra_bits) {
-  if (distance_code < kNumDistanceShortCodes + num_direct_codes) {
-    *code = static_cast<uint16_t>(distance_code);
-    *extra_bits = 0;
-    return;
-  }
-  distance_code -= kNumDistanceShortCodes + num_direct_codes;  /* >= 0 */
-  distance_code += (1u << (postfix_bits + 2u));  /* > 0 */
-  size_t bucket = Log2FloorNonZero(distance_code) - 1;
-  size_t postfix_mask = (1 << postfix_bits) - 1;
-  size_t postfix = distance_code & postfix_mask;
-  size_t prefix = (distance_code >> bucket) & 1;
-  size_t offset = (2 + prefix) << bucket;
-  size_t nbits = bucket - postfix_bits;
-  *code = static_cast<uint16_t>(
-      (kNumDistanceShortCodes + num_direct_codes +
-       ((2 * (nbits - 1) + prefix) << postfix_bits) + postfix));
-  *extra_bits = static_cast<uint32_t>(
-      (nbits << 24) | ((distance_code - offset) >> postfix_bits));
-}
+#if defined(__cplusplus) || defined(c_plusplus)
+}  /* extern "C" */
+#endif
 
-}  // namespace brotli
-
-#endif  // BROTLI_ENC_PREFIX_H_
+#endif  /* BROTLI_ENC_PREFIX_H_ */