Orange Pi5 kernel

^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   2)  * bitstream
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   3)  * Part of FSE library
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   4)  * header file (to include)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   5)  * Copyright (C) 2013-2016, Yann Collet.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   6)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   7)  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   8)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   9)  * Redistribution and use in source and binary forms, with or without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  10)  * modification, are permitted provided that the following conditions are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  11)  * met:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  12)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  13)  *   * Redistributions of source code must retain the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  14)  * notice, this list of conditions and the following disclaimer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  15)  *   * Redistributions in binary form must reproduce the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  16)  * copyright notice, this list of conditions and the following disclaimer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  17)  * in the documentation and/or other materials provided with the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  18)  * distribution.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  19)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  20)  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  21)  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  22)  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  23)  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  24)  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  25)  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  26)  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  27)  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  28)  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  29)  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  30)  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  31)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  32)  * This program is free software; you can redistribute it and/or modify it under
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  33)  * the terms of the GNU General Public License version 2 as published by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  34)  * Free Software Foundation. This program is dual-licensed; you may select
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  35)  * either version 2 of the GNU General Public License ("GPL") or BSD license
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  36)  * ("BSD").
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  37)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  38)  * You can contact the author at :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  39)  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  40)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  41) #ifndef BITSTREAM_H_MODULE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  42) #define BITSTREAM_H_MODULE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  43) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  44) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  45) *  This API consists of small unitary functions, which must be inlined for best performance.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  46) *  Since link-time-optimization is not available for all compilers,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  47) *  these functions are defined into a .h to be included.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  48) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  49) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  50) /*-****************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  51) *  Dependencies
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  52) ******************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  53) #include "error_private.h" /* error codes and messages */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  54) #include "mem.h"	   /* unaligned access routines */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  55) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  56) /*=========================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  57) *  Target specific
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  58) =========================================*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  59) #define STREAM_ACCUMULATOR_MIN_32 25
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  60) #define STREAM_ACCUMULATOR_MIN_64 57
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  61) #define STREAM_ACCUMULATOR_MIN ((U32)(ZSTD_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  62) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  63) /*-******************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  64) *  bitStream encoding API (write forward)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  65) ********************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  66) /* bitStream can mix input from multiple sources.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  67) *  A critical property of these streams is that they encode and decode in **reverse** direction.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  68) *  So the first bit sequence you add will be the last to be read, like a LIFO stack.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  69) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  70) typedef struct {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  71) 	size_t bitContainer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  72) 	int bitPos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  73) 	char *startPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  74) 	char *ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  75) 	char *endPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  76) } BIT_CStream_t;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  77) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  78) ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  79) ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  80) ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  81) ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  82) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  83) /* Start with initCStream, providing the size of buffer to write into.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  84) *  bitStream will never write outside of this buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  85) *  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  86) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  87) *  bits are first added to a local register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  88) *  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  89) *  Writing data into memory is an explicit operation, performed by the flushBits function.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  90) *  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  91) *  After a flushBits, a maximum of 7 bits might still be stored into local register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  92) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  93) *  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  94) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  95) *  Last operation is to close the bitStream.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  96) *  The function returns the final size of CStream in bytes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  97) *  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  98) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  99) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) /*-********************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) *  bitStream decoding API (read backward)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) **********************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) typedef struct {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) 	size_t bitContainer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) 	unsigned bitsConsumed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) 	const char *ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) 	const char *start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) } BIT_DStream_t;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) typedef enum {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) 	BIT_DStream_unfinished = 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) 	BIT_DStream_endOfBuffer = 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) 	BIT_DStream_completed = 2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) 	BIT_DStream_overflow = 3
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) } BIT_DStream_status; /* result of BIT_reloadDStream() */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) /* Start by invoking BIT_initDStream().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) *  A chunk of the bitStream is then stored into a local register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) *  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) *  You can then retrieve bitFields stored into the local register, **in reverse order**.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) *  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) *  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) *  Otherwise, it can be less than that, so proceed accordingly.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) *  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) /*-****************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) *  unsafe API
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) ******************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) /* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) /* unsafe version; does not check buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) /* faster, but works only if nbBits >= 1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) *  Internal functions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - __builtin_clz(val); }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) /*=====    Local Constants   =====*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) static const unsigned BIT_mask[] = {0,       1,       3,       7,	0xF,      0x1F,     0x3F,     0x7F,      0xFF,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) 				    0x1FF,   0x3FF,   0x7FF,   0xFFF,    0x1FFF,   0x3FFF,   0x7FFF,   0xFFFF,    0x1FFFF,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) 				    0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF}; /* up to 26 bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) *  bitStream encoding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) /*! BIT_initCStream() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)  *  `dstCapacity` must be > sizeof(void*)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)  *  @return : 0 if success,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) 			  otherwise an error code (can be tested using ERR_isError() ) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *startPtr, size_t dstCapacity)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) 	bitC->bitContainer = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) 	bitC->bitPos = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) 	bitC->startPtr = (char *)startPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) 	bitC->ptr = bitC->startPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) 	bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) 	if (dstCapacity <= sizeof(bitC->ptr))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) 		return ERROR(dstSize_tooSmall);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) 	return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) /*! BIT_addBits() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) 	can add up to 26 bits into `bitC`.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) 	Does not check for register overflow ! */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) 	bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) 	bitC->bitPos += nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) /*! BIT_addBitsFast() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184)  *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) 	bitC->bitContainer |= value << bitC->bitPos;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) 	bitC->bitPos += nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) /*! BIT_flushBitsFast() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192)  *  unsafe version; does not check buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) 	size_t const nbBytes = bitC->bitPos >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) 	ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) 	bitC->ptr += nbBytes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) 	bitC->bitPos &= 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) 	bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) /*! BIT_flushBits() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203)  *  safe version; check for buffer overflow, and prevents it.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204)  *  note : does not signal buffer overflow. This will be revealed later on using BIT_closeCStream() */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) 	size_t const nbBytes = bitC->bitPos >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) 	ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) 	bitC->ptr += nbBytes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) 	if (bitC->ptr > bitC->endPtr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) 		bitC->ptr = bitC->endPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) 	bitC->bitPos &= 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) 	bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= sizeof(bitContainer)*8 --> undefined behavior */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) /*! BIT_closeCStream() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217)  *  @return : size of CStream, in bytes,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) 			  or 0 if it could not fit into dstBuffer */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) 	BIT_addBitsFast(bitC, 1, 1); /* endMark */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) 	BIT_flushBits(bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) 	if (bitC->ptr >= bitC->endPtr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) 		return 0; /* doesn't fit within authorized budget : cancel */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) 	return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) /*-********************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) * bitStream decoding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) **********************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) /*! BIT_initDStream() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) *   Initialize a BIT_DStream_t.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) *   `bitD` : a pointer to an already allocated BIT_DStream_t structure.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) *   `srcSize` must be the *exact* size of the bitStream, in bytes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) *   @return : size of stream (== srcSize) or an errorCode if a problem is detected
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) 	if (srcSize < 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) 		memset(bitD, 0, sizeof(*bitD));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) 		return ERROR(srcSize_wrong);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) 	if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) 		bitD->start = (const char *)srcBuffer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) 		bitD->ptr = (const char *)srcBuffer + srcSize - sizeof(bitD->bitContainer);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) 		bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) 		{
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) 			BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) 			bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) 			if (lastByte == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) 				return ERROR(GENERIC); /* endMark not present */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) 	} else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) 		bitD->start = (const char *)srcBuffer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) 		bitD->ptr = bitD->start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) 		bitD->bitContainer = *(const BYTE *)(bitD->start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) 		switch (srcSize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) 		case 7: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[6]) << (sizeof(bitD->bitContainer) * 8 - 16);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) 			/* fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) 		case 6: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) 			/* fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) 		case 5: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) 			/* fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) 		case 4: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[3]) << 24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) 			/* fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) 		case 3: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[2]) << 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) 			/* fall through */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) 		case 2: bitD->bitContainer += (size_t)(((const BYTE *)(srcBuffer))[1]) << 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) 		default:;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) 		{
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) 			BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) 			bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) 			if (lastByte == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) 				return ERROR(GENERIC); /* endMark not present */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) 		bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize) * 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) 	return srcSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { return bitContainer >> start; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { return bitContainer & BIT_mask[nbBits]; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) /*! BIT_lookBits() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)  *  Provides next n bits from local register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)  *  local register is not modified.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)  *  On 32-bits, maxNbBits==24.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296)  *  On 64-bits, maxNbBits==56.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)  *  @return : value extracted
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) 	U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) 	return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask - nbBits) & bitMask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) /*! BIT_lookBitsFast() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) *   unsafe version; only works only if nbBits >= 1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) 	U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) 	return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask + 1) - nbBits) & bitMask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { bitD->bitsConsumed += nbBits; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) /*! BIT_readBits() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)  *  Read (consume) next n bits from local register and update.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)  *  Pay attention to not read more than nbBits contained into local register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318)  *  @return : extracted value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) 	size_t const value = BIT_lookBits(bitD, nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) 	BIT_skipBits(bitD, nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) 	return value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) /*! BIT_readBitsFast() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) *   unsafe version; only works only if nbBits >= 1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) 	size_t const value = BIT_lookBitsFast(bitD, nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) 	BIT_skipBits(bitD, nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) 	return value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) /*! BIT_reloadDStream() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) *   Refill `bitD` from buffer previously set in BIT_initDStream() .
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) *   This function is safe, it guarantees it will not read beyond src buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) *   @return : status of `BIT_DStream_t` internal register.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) 			  if status == BIT_DStream_unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) 	if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should not happen => corruption detected */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) 		return BIT_DStream_overflow;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) 	if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) 		bitD->ptr -= bitD->bitsConsumed >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) 		bitD->bitsConsumed &= 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) 		bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) 		return BIT_DStream_unfinished;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) 	if (bitD->ptr == bitD->start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) 		if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) 			return BIT_DStream_endOfBuffer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) 		return BIT_DStream_completed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) 	{
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) 		U32 nbBytes = bitD->bitsConsumed >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) 		BIT_DStream_status result = BIT_DStream_unfinished;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) 		if (bitD->ptr - nbBytes < bitD->start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) 			nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) 			result = BIT_DStream_endOfBuffer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) 		bitD->ptr -= nbBytes;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) 		bitD->bitsConsumed -= nbBytes * 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) 		bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) 		return result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) /*! BIT_endOfDStream() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) *   @return Tells if DStream has exactly reached its end (all bits consumed).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) 	return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer) * 8));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) #endif /* BITSTREAM_H_MODULE */