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.11; 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 2015 Google Inc. All Rights Reserved. Distributed under MIT license. See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ /* Algorithms for distributing the literals and commands of a metablock between block types and contexts. */ #include "./memory.h" #include /* exit, free, malloc */ #include /* memcpy */ #include "../common/platform.h" #include #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif #define MAX_PERM_ALLOCATED 128 #define MAX_NEW_ALLOCATED 64 #define MAX_NEW_FREED 64 #define PERM_ALLOCATED_OFFSET 0 #define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED #define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED) void BrotliInitMemoryManager( MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { if (!alloc_func) { m->alloc_func = BrotliDefaultAllocFunc; m->free_func = BrotliDefaultFreeFunc; m->opaque = 0; } else { m->alloc_func = alloc_func; m->free_func = free_func; m->opaque = opaque; } #if !defined(BROTLI_ENCODER_EXIT_ON_OOM) m->is_oom = BROTLI_FALSE; m->perm_allocated = 0; m->new_allocated = 0; m->new_freed = 0; #endif /* BROTLI_ENCODER_EXIT_ON_OOM */ } #if defined(BROTLI_ENCODER_EXIT_ON_OOM) void* BrotliAllocate(MemoryManager* m, size_t n) { void* result = m->alloc_func(m->opaque, n); if (!result) exit(EXIT_FAILURE); return result; } void BrotliFree(MemoryManager* m, void* p) { m->free_func(m->opaque, p); } void BrotliWipeOutMemoryManager(MemoryManager* m) { BROTLI_UNUSED(m); } #else /* BROTLI_ENCODER_EXIT_ON_OOM */ static void SortPointers(void** items, const size_t n) { /* Shell sort. */ static const size_t gaps[] = {23, 10, 4, 1}; int g = 0; for (; g < 4; ++g) { size_t gap = gaps[g]; size_t i; for (i = gap; i < n; ++i) { size_t j = i; void* tmp = items[i]; for (; j >= gap && tmp < items[j - gap]; j -= gap) { items[j] = items[j - gap]; } items[j] = tmp; } } } static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) { size_t a_read_index = 0; size_t b_read_index = 0; size_t a_write_index = 0; size_t b_write_index = 0; size_t annihilated = 0; while (a_read_index < a_len && b_read_index < b_len) { if (a[a_read_index] == b[b_read_index]) { a_read_index++; b_read_index++; annihilated++; } else if (a[a_read_index] < b[b_read_index]) { a[a_write_index++] = a[a_read_index++]; } else { b[b_write_index++] = b[b_read_index++]; } } while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++]; while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++]; return annihilated; } static void CollectGarbagePointers(MemoryManager* m) { size_t annihilated; SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated); SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed); annihilated = Annihilate( m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated, m->pointers + NEW_FREED_OFFSET, m->new_freed); m->new_allocated -= annihilated; m->new_freed -= annihilated; if (m->new_freed != 0) { annihilated = Annihilate( m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated, m->pointers + NEW_FREED_OFFSET, m->new_freed); m->perm_allocated -= annihilated; m->new_freed -= annihilated; BROTLI_DCHECK(m->new_freed == 0); } if (m->new_allocated != 0) { BROTLI_DCHECK(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED); memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated, m->pointers + NEW_ALLOCATED_OFFSET, sizeof(void*) * m->new_allocated); m->perm_allocated += m->new_allocated; m->new_allocated = 0; SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated); } } void* BrotliAllocate(MemoryManager* m, size_t n) { void* result = m->alloc_func(m->opaque, n); if (!result) { m->is_oom = BROTLI_TRUE; return NULL; } if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m); m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result; return result; } void BrotliFree(MemoryManager* m, void* p) { if (!p) return; m->free_func(m->opaque, p); if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m); m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p; } void BrotliWipeOutMemoryManager(MemoryManager* m) { size_t i; CollectGarbagePointers(m); /* Now all unfreed pointers are in perm-allocated list. */ for (i = 0; i < m->perm_allocated; ++i) { m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]); } m->perm_allocated = 0; } #endif /* BROTLI_ENCODER_EXIT_ON_OOM */ #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 @@