c/enc/backward_references.c

/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Function to find backward reference copies. */

#include "backward_references.h"

#include "../common/constants.h"
#include "../common/context.h"
#include "../common/platform.h"
#include "command.h"
#include "compound_dictionary.h"
#include "encoder_dict.h"
#include "hash.h"
#include "params.h"
#include "quality.h"  /* IWYU pragma: keep for inc */

BROTLI_INTERNAL const BROTLI_MODEL("small")
    uint8_t kIsBase64[256] = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
        0, 0, 0, 1, /* 43 '+', 47 '/' (45 '-' is 0) */
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 48-57 '0'-'9' (61 '='
                                                           is 0) */
        0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 65-79 'A'-'O' */
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 80-90 'P'-'Z' */
        0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 97-111 'a'-'o' */
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 112-122 'p'-'z' */
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

static const size_t kBase64TriggerLen = 8;

/* Minimum payload length (in bytes) required for Base64 block deduplication.
   Blocks shorter than 32 bytes do not yield sufficient entropy reduction to
   amortize the backward reference command encoding overhead and are skipped. */
static const size_t kMinBase64DeduplicationLen = 32;

static BROTLI_INLINE BROTLI_BOOL IsBase64Char(uint8_t c) {
  return TO_BROTLI_BOOL(kIsBase64[c]);
}

static BROTLI_INLINE BROTLI_BOOL MatchTrigger(const uint8_t* ringbuffer,
                                              size_t mask, size_t pos) {
  const char* trigger = ";base64,";
  size_t i;
  for (i = 0; i < kBase64TriggerLen; ++i) {
    if (ringbuffer[(pos + i) & mask] != trigger[i]) return BROTLI_FALSE;
  }
  return BROTLI_TRUE;
}

static size_t FindNextBase64Trigger(const uint8_t* ringbuffer, size_t mask,
                                    size_t pos, size_t end) {
  while (pos + kBase64TriggerLen <= end) {
    size_t ringbuffer_size = mask + 1;
    size_t pos_index = pos & mask;
    size_t contiguous_len = ringbuffer_size - pos_index;
    size_t max_scan_len = end - pos;
    size_t scan_len = BROTLI_MIN(size_t, contiguous_len, max_scan_len);

    const uint8_t* p =
        (const uint8_t*)memchr(&ringbuffer[pos_index], ';', scan_len);
    if (p != NULL) {
      size_t offset = (size_t)(p - &ringbuffer[pos_index]);
      if (pos + offset + kBase64TriggerLen <= end) {
        if (MatchTrigger(ringbuffer, mask, pos + offset)) {
          return pos + offset;
        }
      } else {
        return end;
      }
      pos += offset + 1;
    } else {
      pos += scan_len;
    }
  }
  return end;
}

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

static BROTLI_INLINE size_t ComputeDistanceCode(size_t distance,
                                                size_t max_distance,
                                                const int* dist_cache) {
  if (distance <= max_distance) {
    size_t distance_plus_3 = distance + 3;
    size_t offset0 = distance_plus_3 - (size_t)dist_cache[0];
    size_t offset1 = distance_plus_3 - (size_t)dist_cache[1];
    if (distance == (size_t)dist_cache[0]) {
      return 0;
    } else if (distance == (size_t)dist_cache[1]) {
      return 1;
    } else if (offset0 < 7) {
      return (0x9750468 >> (4 * offset0)) & 0xF;
    } else if (offset1 < 7) {
      return (0xFDB1ACE >> (4 * offset1)) & 0xF;
    } else if (distance == (size_t)dist_cache[2]) {
      return 2;
    } else if (distance == (size_t)dist_cache[3]) {
      return 3;
    }
  }
  return distance + BROTLI_NUM_DISTANCE_SHORT_CODES - 1;
}

static BROTLI_INLINE BROTLI_BOOL RingBufferCompare(
    const uint8_t* ringbuffer, size_t mask,
    size_t pos1, size_t pos2, size_t length) {
  size_t rb_size = mask + 1;
  while (length > 0) {
    size_t idx1 = pos1 & mask;
    size_t idx2 = pos2 & mask;
    size_t contig1 = rb_size - idx1;
    size_t contig2 = rb_size - idx2;
    size_t chunk = BROTLI_MIN(size_t, length, contig1);
    chunk = BROTLI_MIN(size_t, chunk, contig2);
    if (memcmp(&ringbuffer[idx1], &ringbuffer[idx2], chunk) != 0) {
      return BROTLI_FALSE;
    }
    pos1 += chunk;
    pos2 += chunk;
    length -= chunk;
  }
  return BROTLI_TRUE;
}

#define EXPAND_CAT(a, b) CAT(a, b)
#define CAT(a, b) a ## b
#define FN(X) EXPAND_CAT(X, HASHER())
#define EXPORT_FN(X) EXPAND_CAT(X, EXPAND_CAT(PREFIX(), HASHER()))

#define PREFIX() N
#define ENABLE_COMPOUND_DICTIONARY 0

#define HASHER() H2
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H3
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H4
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H5
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H6
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H40
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H41
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H42
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H54
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H35
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H55
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H65
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#if defined(BROTLI_MAX_SIMD_QUALITY)
#define HASHER() H58
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER

#define HASHER() H68
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#endif

#undef ENABLE_COMPOUND_DICTIONARY
#undef PREFIX
#define PREFIX() D
#define ENABLE_COMPOUND_DICTIONARY 1

#define HASHER() H3
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H4
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H5
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H6
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H40
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H41
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H42
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H55
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H65
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#if defined(BROTLI_MAX_SIMD_QUALITY)
#define HASHER() H58
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#define HASHER() H68
/* NOLINTNEXTLINE(build/include) */
#include "backward_references_inc.h"
#undef HASHER
#endif

#undef ENABLE_COMPOUND_DICTIONARY
#undef PREFIX

#undef EXPORT_FN
#undef FN
#undef CAT
#undef EXPAND_CAT

void BrotliCreateBackwardReferences(size_t num_bytes,
    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
    ContextLut literal_context_lut, const BrotliEncoderParams* params,
    Hasher* hasher, int* dist_cache, size_t* last_insert_len,
    Command* commands, size_t* num_commands, size_t* num_literals) {
  if (params->dictionary.compound.num_chunks != 0) {
    switch (params->hasher.type) {
#define CASE_(N)                                                    \
      case N:                                                       \
        CreateBackwardReferencesDH ## N(num_bytes,                  \
            position, ringbuffer, ringbuffer_mask,                  \
            literal_context_lut, params, hasher, dist_cache,        \
            last_insert_len, commands, num_commands, num_literals); \
        return;
      CASE_(3)
      CASE_(4)
      CASE_(5)
      CASE_(6)
#if defined(BROTLI_MAX_SIMD_QUALITY)
      CASE_(58)
      CASE_(68)
#endif
      CASE_(40)
      CASE_(41)
      CASE_(42)
      CASE_(55)
      CASE_(65)
#undef CASE_
      default:
        BROTLI_DCHECK(BROTLI_FALSE);
        break;
    }
  }

  switch (params->hasher.type) {
#define CASE_(N)                                                  \
    case N:                                                       \
      CreateBackwardReferencesNH ## N(num_bytes,                  \
          position, ringbuffer, ringbuffer_mask,                  \
          literal_context_lut, params, hasher, dist_cache,        \
          last_insert_len, commands, num_commands, num_literals); \
      return;
    FOR_GENERIC_HASHERS(CASE_)
#undef CASE_
    default:
      BROTLI_DCHECK(BROTLI_FALSE);
      break;
  }
}

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif