head	1.2;
access;
symbols
	netbsd-11-1-RELEASE:1.1.1.1.2.1
	netbsd-11-0-RELEASE:1.1.1.1
	netbsd-11-0-RC7:1.1.1.1
	netbsd-11-0-RC6:1.1.1.1
	netbsd-11-0-RC5:1.1.1.1
	netbsd-11-0-RC4:1.1.1.1
	netbsd-11-0-RC3:1.1.1.1
	netbsd-11-0-RC2:1.1.1.1
	netbsd-11-0-RC1:1.1.1.1
	netbsd-11:1.1.1.1.0.2
	netbsd-11-base:1.1.1.1
	brotli-1-0-9:1.1.1.1
	GOOGLE:1.1.1;
locks; strict;
comment	@ * @;


1.2
date	2026.10.28.21.13.09;	author mrg;	state dead;
branches;
next	1.1;
commitid	WySy0JIemcP5Wh1H;

1.1
date	2023.01.29.06.38.34;	author mrg;	state Exp;
branches
	1.1.1.1;
next	;
commitid	gOcuvoN6w4Ry1pbE;

1.1.1.1
date	2023.01.29.06.38.34;	author mrg;	state Exp;
branches
	1.1.1.1.2.1;
next	;
commitid	gOcuvoN6w4Ry1pbE;

1.1.1.1.2.1
date	2026.10.29.16.03.51;	author martin;	state dead;
branches;
next	;
commitid	Zd6vMoBhuWqLbo1H;


desc
@@


1.2
log
@merge brotli 1.2.1.
@
text
@/* Copyright 2013 Google Inc. All Rights Reserved.

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

/* Block split point selection utilities. */

#include "./block_splitter.h"

#include <string.h>  /* memcpy, memset */

#include "../common/platform.h"
#include "./bit_cost.h"
#include "./cluster.h"
#include "./command.h"
#include "./fast_log.h"
#include "./histogram.h"
#include "./memory.h"
#include "./quality.h"

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

static const size_t kMaxLiteralHistograms = 100;
static const size_t kMaxCommandHistograms = 50;
static const double kLiteralBlockSwitchCost = 28.1;
static const double kCommandBlockSwitchCost = 13.5;
static const double kDistanceBlockSwitchCost = 14.6;
static const size_t kLiteralStrideLength = 70;
static const size_t kCommandStrideLength = 40;
static const size_t kSymbolsPerLiteralHistogram = 544;
static const size_t kSymbolsPerCommandHistogram = 530;
static const size_t kSymbolsPerDistanceHistogram = 544;
static const size_t kMinLengthForBlockSplitting = 128;
static const size_t kIterMulForRefining = 2;
static const size_t kMinItersForRefining = 100;

static size_t CountLiterals(const Command* cmds, const size_t num_commands) {
  /* Count how many we have. */
  size_t total_length = 0;
  size_t i;
  for (i = 0; i < num_commands; ++i) {
    total_length += cmds[i].insert_len_;
  }
  return total_length;
}

static void CopyLiteralsToByteArray(const Command* cmds,
                                    const size_t num_commands,
                                    const uint8_t* data,
                                    const size_t offset,
                                    const size_t mask,
                                    uint8_t* literals) {
  size_t pos = 0;
  size_t from_pos = offset & mask;
  size_t i;
  for (i = 0; i < num_commands; ++i) {
    size_t insert_len = cmds[i].insert_len_;
    if (from_pos + insert_len > mask) {
      size_t head_size = mask + 1 - from_pos;
      memcpy(literals + pos, data + from_pos, head_size);
      from_pos = 0;
      pos += head_size;
      insert_len -= head_size;
    }
    if (insert_len > 0) {
      memcpy(literals + pos, data + from_pos, insert_len);
      pos += insert_len;
    }
    from_pos = (from_pos + insert_len + CommandCopyLen(&cmds[i])) & mask;
  }
}

static BROTLI_INLINE uint32_t MyRand(uint32_t* seed) {
  /* Initial seed should be 7. In this case, loop length is (1 << 29). */
  *seed *= 16807U;
  return *seed;
}

static BROTLI_INLINE double BitCost(size_t count) {
  return count == 0 ? -2.0 : FastLog2(count);
}

#define HISTOGRAMS_PER_BATCH 64
#define CLUSTERS_PER_BATCH 16

#define FN(X) X ## Literal
#define DataType uint8_t
/* NOLINTNEXTLINE(build/include) */
#include "./block_splitter_inc.h"
#undef DataType
#undef FN

#define FN(X) X ## Command
#define DataType uint16_t
/* NOLINTNEXTLINE(build/include) */
#include "./block_splitter_inc.h"
#undef FN

#define FN(X) X ## Distance
/* NOLINTNEXTLINE(build/include) */
#include "./block_splitter_inc.h"
#undef DataType
#undef FN

void BrotliInitBlockSplit(BlockSplit* self) {
  self->num_types = 0;
  self->num_blocks = 0;
  self->types = 0;
  self->lengths = 0;
  self->types_alloc_size = 0;
  self->lengths_alloc_size = 0;
}

void BrotliDestroyBlockSplit(MemoryManager* m, BlockSplit* self) {
  BROTLI_FREE(m, self->types);
  BROTLI_FREE(m, self->lengths);
}

void BrotliSplitBlock(MemoryManager* m,
                      const Command* cmds,
                      const size_t num_commands,
                      const uint8_t* data,
                      const size_t pos,
                      const size_t mask,
                      const BrotliEncoderParams* params,
                      BlockSplit* literal_split,
                      BlockSplit* insert_and_copy_split,
                      BlockSplit* dist_split) {
  {
    size_t literals_count = CountLiterals(cmds, num_commands);
    uint8_t* literals = BROTLI_ALLOC(m, uint8_t, literals_count);
    if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(literals)) return;
    /* Create a continuous array of literals. */
    CopyLiteralsToByteArray(cmds, num_commands, data, pos, mask, literals);
    /* Create the block split on the array of literals.
       Literal histograms have alphabet size 256. */
    SplitByteVectorLiteral(
        m, literals, literals_count,
        kSymbolsPerLiteralHistogram, kMaxLiteralHistograms,
        kLiteralStrideLength, kLiteralBlockSwitchCost, params,
        literal_split);
    if (BROTLI_IS_OOM(m)) return;
    BROTLI_FREE(m, literals);
  }

  {
    /* Compute prefix codes for commands. */
    uint16_t* insert_and_copy_codes = BROTLI_ALLOC(m, uint16_t, num_commands);
    size_t i;
    if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(insert_and_copy_codes)) return;
    for (i = 0; i < num_commands; ++i) {
      insert_and_copy_codes[i] = cmds[i].cmd_prefix_;
    }
    /* Create the block split on the array of command prefixes. */
    SplitByteVectorCommand(
        m, insert_and_copy_codes, num_commands,
        kSymbolsPerCommandHistogram, kMaxCommandHistograms,
        kCommandStrideLength, kCommandBlockSwitchCost, params,
        insert_and_copy_split);
    if (BROTLI_IS_OOM(m)) return;
    /* TODO: reuse for distances? */
    BROTLI_FREE(m, insert_and_copy_codes);
  }

  {
    /* Create a continuous array of distance prefixes. */
    uint16_t* distance_prefixes = BROTLI_ALLOC(m, uint16_t, num_commands);
    size_t j = 0;
    size_t i;
    if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(distance_prefixes)) return;
    for (i = 0; i < num_commands; ++i) {
      const Command* cmd = &cmds[i];
      if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {
        distance_prefixes[j++] = cmd->dist_prefix_ & 0x3FF;
      }
    }
    /* Create the block split on the array of distance prefixes. */
    SplitByteVectorDistance(
        m, distance_prefixes, j,
        kSymbolsPerDistanceHistogram, kMaxCommandHistograms,
        kCommandStrideLength, kDistanceBlockSwitchCost, params,
        dist_split);
    if (BROTLI_IS_OOM(m)) return;
    BROTLI_FREE(m, distance_prefixes);
  }
}


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


1.1
log
@Initial revision
@
text
@@


1.1.1.1
log
@initial import of brotli 1.0.9.

modern blender wants freetype to have brotli support enabled or it
won't build.  fortunately, enabling the decoder support (all it
needs currently) is relatively easy and small (~160k on amd64)
without exposing brotli as a first class citizen is easy, so this
will be linked into xsrc freetype directly.

XXX: pullup-10?  or perhaps force -10 to use pkgsrc freetype?

from pkgsrc DESCR:
Brotli is a generic-purpose lossless compression algorithm that compresses data
using a combination of a modern variant of the LZ77 algorithm, Huffman coding
and 2nd order context modeling, with a compression ratio comparable to the best
currently available general-purpose compression methods. It is similar in speed
with deflate but offers more dense compression.
@
text
@@


1.1.1.1.2.1
log
@Pull up the following, requested by mrg in ticket #562:

	external/mit/brotli/dist/BUILD.bazel            up to 1.1.1.1
	external/mit/brotli/dist/c/common/dictionary_inc.h up to 1.1.1.1
	external/mit/brotli/dist/c/common/shared_dictionary.c up to 1.1.1.1
	external/mit/brotli/dist/c/common/shared_dictionary_internal.h up to 1.1.1.1
	external/mit/brotli/dist/c/common/static_init.h up to 1.1.1.1
	external/mit/brotli/dist/c/dec/prefix.c         up to 1.1.1.1
	external/mit/brotli/dist/c/dec/prefix_inc.h     up to 1.1.1.1
	external/mit/brotli/dist/c/dec/static_init.c    up to 1.1.1.1
	external/mit/brotli/dist/c/dec/static_init.h    up to 1.1.1.1
	external/mit/brotli/dist/c/include/brotli/shared_dictionary.h up to 1.1.1.1
	external/mit/brotli/dist/docs/brotli.svg        up to 1.1.1.1
	external/mit/brotli/dist/scripts/download_testdata.sh up to 1.1.1.1
	external/mit/brotli/dist/tests/testdata/zerosukkanooa.compressed up to 1.1.1.1
	external/mit/brotli/dist/tests/cli_test.sh      up to 1.1.1.1
	external/mit/brotli/dist/SECURITY.md            up to 1.1.1.1
	external/mit/brotli/dist/.bazelignore           up to 1.1.1.1
	external/mit/brotli/dist/CHANGELOG.md           up to 1.1.1.1
	external/mit/brotli/dist/BUILD                  delete
	external/mit/brotli/dist/Makefile               delete
	external/mit/brotli/dist/Makefile.am            delete
	external/mit/brotli/dist/WORKSPACE              delete
	external/mit/brotli/dist/bootstrap              delete
	external/mit/brotli/dist/compiler_config_setting.bzl delete
	external/mit/brotli/dist/configure              delete
	external/mit/brotli/dist/configure-cmake        delete
	external/mit/brotli/dist/configure.ac           delete
	external/mit/brotli/dist/premake5.lua           delete
	external/mit/brotli/dist/c/enc/backward_references.c delete
	external/mit/brotli/dist/c/enc/backward_references.h delete
	external/mit/brotli/dist/c/enc/backward_references_hq.c delete
	external/mit/brotli/dist/c/enc/backward_references_hq.h delete
	external/mit/brotli/dist/c/enc/backward_references_inc.h delete
	external/mit/brotli/dist/c/enc/bit_cost.c       delete
	external/mit/brotli/dist/c/enc/bit_cost.h       delete
	external/mit/brotli/dist/c/enc/bit_cost_inc.h   delete
	external/mit/brotli/dist/c/enc/block_encoder_inc.h delete
	external/mit/brotli/dist/c/enc/block_splitter.c delete
	external/mit/brotli/dist/c/enc/block_splitter.h delete
	external/mit/brotli/dist/c/enc/block_splitter_inc.h delete
	external/mit/brotli/dist/c/enc/brotli_bit_stream.c delete
	external/mit/brotli/dist/c/enc/brotli_bit_stream.h delete
	external/mit/brotli/dist/c/enc/cluster.c        delete
	external/mit/brotli/dist/c/enc/cluster.h        delete
	external/mit/brotli/dist/c/enc/cluster_inc.h    delete
	external/mit/brotli/dist/c/enc/command.c        delete
	external/mit/brotli/dist/c/enc/command.h        delete
	external/mit/brotli/dist/c/enc/compress_fragment.c delete
	external/mit/brotli/dist/c/enc/compress_fragment.h delete
	external/mit/brotli/dist/c/enc/compress_fragment_two_pass.c delete
	external/mit/brotli/dist/c/enc/compress_fragment_two_pass.h delete
	external/mit/brotli/dist/c/enc/dictionary_hash.c delete
	external/mit/brotli/dist/c/enc/dictionary_hash.h delete
	external/mit/brotli/dist/c/enc/encode.c         delete
	external/mit/brotli/dist/c/enc/encoder_dict.c   delete
	external/mit/brotli/dist/c/enc/encoder_dict.h   delete
	external/mit/brotli/dist/c/enc/entropy_encode.c delete
	external/mit/brotli/dist/c/enc/entropy_encode.h delete
	external/mit/brotli/dist/c/enc/entropy_encode_static.h delete
	external/mit/brotli/dist/c/enc/fast_log.c       delete
	external/mit/brotli/dist/c/enc/fast_log.h       delete
	external/mit/brotli/dist/c/enc/find_match_length.h delete
	external/mit/brotli/dist/c/enc/hash.h           delete
	external/mit/brotli/dist/c/enc/hash_composite_inc.h delete
	external/mit/brotli/dist/c/enc/hash_forgetful_chain_inc.h delete
	external/mit/brotli/dist/c/enc/hash_longest_match64_inc.h delete
	external/mit/brotli/dist/c/enc/hash_longest_match_inc.h delete
	external/mit/brotli/dist/c/enc/hash_longest_match_quickly_inc.h delete
	external/mit/brotli/dist/c/enc/hash_rolling_inc.h delete
	external/mit/brotli/dist/c/enc/hash_to_binary_tree_inc.h delete
	external/mit/brotli/dist/c/enc/histogram.c      delete
	external/mit/brotli/dist/c/enc/histogram.h      delete
	external/mit/brotli/dist/c/enc/histogram_inc.h  delete
	external/mit/brotli/dist/c/enc/literal_cost.c   delete
	external/mit/brotli/dist/c/enc/literal_cost.h   delete
	external/mit/brotli/dist/c/enc/memory.c         delete
	external/mit/brotli/dist/c/enc/memory.h         delete
	external/mit/brotli/dist/c/enc/metablock.c      delete
	external/mit/brotli/dist/c/enc/metablock.h      delete
	external/mit/brotli/dist/c/enc/metablock_inc.h  delete
	external/mit/brotli/dist/c/enc/params.h         delete
	external/mit/brotli/dist/c/enc/prefix.h         delete
	external/mit/brotli/dist/c/enc/quality.h        delete
	external/mit/brotli/dist/c/enc/utf8_util.c      delete
	external/mit/brotli/dist/c/enc/ringbuffer.h     delete
	external/mit/brotli/dist/c/enc/static_dict.c    delete
	external/mit/brotli/dist/c/enc/static_dict.h    delete
	external/mit/brotli/dist/c/enc/static_dict_lut.h delete
	external/mit/brotli/dist/c/enc/utf8_util.h      delete
	external/mit/brotli/dist/c/enc/write_bits.h     delete
	external/mit/brotli/dist/python/Makefile        delete
	external/mit/brotli/dist/python/README.md       delete
	external/mit/brotli/dist/python/_brotli.cc      delete
	external/mit/brotli/dist/python/bro.py          delete
	external/mit/brotli/dist/python/brotli.py       delete
	external/mit/brotli/dist/python/tests/__init__.py delete
	external/mit/brotli/dist/python/tests/_test_utils.py delete
	external/mit/brotli/dist/python/tests/bro_test.py delete
	external/mit/brotli/dist/python/tests/compress_test.py delete
	external/mit/brotli/dist/python/tests/compressor_test.py delete
	external/mit/brotli/dist/python/tests/decompress_test.py delete
	external/mit/brotli/dist/python/tests/decompressor_test.py delete
	external/mit/brotli/dist/scripts/sources.lst    delete
	external/mit/brotli/dist/tests/Makefile         delete
	external/mit/brotli/dist/tests/compatibility_test.sh delete
	external/mit/brotli/dist/tests/roundtrip_test.sh delete
	external/mit/brotli/dist/CMakeLists.txt         up to 1.1.1.2
	external/mit/brotli/dist/CONTRIBUTING.md        up to 1.1.1.2
	external/mit/brotli/dist/MANIFEST.in            up to 1.1.1.2
	external/mit/brotli/dist/README                 up to 1.1.1.2
	external/mit/brotli/dist/README.md              up to 1.1.1.2
	external/mit/brotli/dist/setup.cfg              up to 1.1.1.2
	external/mit/brotli/dist/setup.py               up to 1.1.1.2
	external/mit/brotli/dist/c/common/constants.c   up to 1.1.1.2
	external/mit/brotli/dist/c/common/constants.h   up to 1.1.1.2
	external/mit/brotli/dist/c/common/context.c     up to 1.1.1.2
	external/mit/brotli/dist/c/common/context.h     up to 1.1.1.2
	external/mit/brotli/dist/c/common/dictionary.c  up to 1.1.1.2
	external/mit/brotli/dist/c/common/dictionary.h  up to 1.1.1.2
	external/mit/brotli/dist/c/common/platform.c    up to 1.1.1.2
	external/mit/brotli/dist/c/common/platform.h    up to 1.2
	external/mit/brotli/dist/c/common/transform.c   up to 1.1.1.2
	external/mit/brotli/dist/c/common/transform.h   up to 1.1.1.2
	external/mit/brotli/dist/c/common/version.h     up to 1.1.1.2
	external/mit/brotli/dist/c/dec/bit_reader.c     up to 1.1.1.2
	external/mit/brotli/dist/c/dec/bit_reader.h     up to 1.1.1.2
	external/mit/brotli/dist/c/dec/decode.c         up to 1.1.1.2
	external/mit/brotli/dist/c/dec/huffman.c        up to 1.1.1.2
	external/mit/brotli/dist/c/dec/huffman.h        up to 1.1.1.2
	external/mit/brotli/dist/c/dec/prefix.h         up to 1.1.1.2
	external/mit/brotli/dist/c/dec/state.c          up to 1.1.1.2
	external/mit/brotli/dist/c/dec/state.h          up to 1.1.1.2
	external/mit/brotli/dist/c/include/brotli/decode.h up to 1.1.1.2
	external/mit/brotli/dist/c/include/brotli/encode.h up to 1.1.1.2
	external/mit/brotli/dist/c/include/brotli/port.h up to 1.1.1.2
	external/mit/brotli/dist/c/include/brotli/types.h up to 1.1.1.2
	external/mit/brotli/dist/c/tools/brotli.c       up to 1.1.1.2
	external/mit/brotli/dist/c/tools/brotli.md      up to 1.1.1.2
	external/mit/brotli/dist/docs/brotli.1          up to 1.1.1.2
	external/mit/brotli/dist/docs/constants.h.3     up to 1.1.1.2
	external/mit/brotli/dist/docs/decode.h.3        up to 1.1.1.2
	external/mit/brotli/dist/docs/encode.h.3        up to 1.1.1.2
	external/mit/brotli/dist/docs/types.h.3         up to 1.1.1.2
	external/mit/brotli/dist/scripts/libbrotlicommon.pc.in up to 1.1.1.2
	external/mit/brotli/dist/scripts/libbrotlidec.pc.in up to 1.1.1.2
	external/mit/brotli/dist/scripts/libbrotlienc.pc.in up to 1.1.1.2

Initial import of brotli 1.2.1, that fixes CVE 2026-111497.
@
text
@@

