bitstream.h 15 KB

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