contrib/python-zstandard/zstd/common/bitstream.h
author Gregory Szorc <gregory.szorc@gmail.com>
Mon, 24 Sep 2018 14:31:31 -0700
changeset 39878 3e896b51aa5d
parent 37495 b1fb341d8a61
child 40121 73fef626dae3
permissions -rw-r--r--
storageutil: move metadata parsing and packing from revlog (API) Parsing and writing of revision text metadata is likely identical across storage backends. Let's move the code out of revlog so we don't need to import the revlog module in order to use it. Differential Revision: https://phab.mercurial-scm.org/D4754
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     1
/* ******************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     2
   bitstream
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     3
   Part of FSE library
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     4
   header file (to include)
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
     5
   Copyright (C) 2013-2017, Yann Collet.
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     6
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     7
   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     8
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
     9
   Redistribution and use in source and binary forms, with or without
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    10
   modification, are permitted provided that the following conditions are
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    11
   met:
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    12
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    13
       * Redistributions of source code must retain the above copyright
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    14
   notice, this list of conditions and the following disclaimer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    15
       * Redistributions in binary form must reproduce the above
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    16
   copyright notice, this list of conditions and the following disclaimer
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    17
   in the documentation and/or other materials provided with the
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    18
   distribution.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    19
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    20
   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    21
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    22
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    23
   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    24
   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    25
   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    26
   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    27
   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    28
   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    29
   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    30
   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    31
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    32
   You can contact the author at :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    33
   - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    34
****************************************************************** */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    35
#ifndef BITSTREAM_H_MODULE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    36
#define BITSTREAM_H_MODULE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    37
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    38
#if defined (__cplusplus)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    39
extern "C" {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    40
#endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    41
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    42
/*
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    43
*  This API consists of small unitary functions, which must be inlined for best performance.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    44
*  Since link-time-optimization is not available for all compilers,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    45
*  these functions are defined into a .h to be included.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    46
*/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    47
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    48
/*-****************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    49
*  Dependencies
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    50
******************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    51
#include "mem.h"            /* unaligned access routines */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    52
#include "error_private.h"  /* error codes and messages */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    53
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    54
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    55
/*-*************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    56
*  Debug
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    57
***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    58
#if defined(BIT_DEBUG) && (BIT_DEBUG>=1)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    59
#  include <assert.h>
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    60
#else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    61
#  ifndef assert
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    62
#    define assert(condition) ((void)0)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    63
#  endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    64
#endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    65
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    66
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    67
/*=========================================
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    68
*  Target specific
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    69
=========================================*/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    70
#if defined(__BMI__) && defined(__GNUC__)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    71
#  include <immintrin.h>   /* support for bextr (experimental) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    72
#endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    73
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    74
#define STREAM_ACCUMULATOR_MIN_32  25
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    75
#define STREAM_ACCUMULATOR_MIN_64  57
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    76
#define STREAM_ACCUMULATOR_MIN    ((U32)(MEM_32bits() ? STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    77
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    78
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    79
/*-******************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    80
*  bitStream encoding API (write forward)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    81
********************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    82
/* bitStream can mix input from multiple sources.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    83
 * A critical property of these streams is that they encode and decode in **reverse** direction.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    84
 * So the first bit sequence you add will be the last to be read, like a LIFO stack.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    85
 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    86
typedef struct
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    87
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    88
    size_t bitContainer;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
    89
    unsigned bitPos;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    90
    char*  startPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    91
    char*  ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    92
    char*  endPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    93
} BIT_CStream_t;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    94
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    95
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC, void* dstBuffer, size_t dstCapacity);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    96
MEM_STATIC void   BIT_addBits(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    97
MEM_STATIC void   BIT_flushBits(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    98
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
    99
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   100
/* Start with initCStream, providing the size of buffer to write into.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   101
*  bitStream will never write outside of this buffer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   102
*  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will be an error code.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   103
*
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   104
*  bits are first added to a local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   105
*  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 32-bits systems.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   106
*  Writing data into memory is an explicit operation, performed by the flushBits function.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   107
*  Hence keep track how many bits are potentially stored into local register to avoid register overflow.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   108
*  After a flushBits, a maximum of 7 bits might still be stored into local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   109
*
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   110
*  Avoid storing elements of more than 24 bits if you want compatibility with 32-bits bitstream readers.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   111
*
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   112
*  Last operation is to close the bitStream.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   113
*  The function returns the final size of CStream in bytes.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   114
*  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   115
*/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   116
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   117
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   118
/*-********************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   119
*  bitStream decoding API (read backward)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   120
**********************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   121
typedef struct
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   122
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   123
    size_t   bitContainer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   124
    unsigned bitsConsumed;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   125
    const char* ptr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   126
    const char* start;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   127
    const char* limitPtr;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   128
} BIT_DStream_t;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   129
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   130
typedef enum { BIT_DStream_unfinished = 0,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   131
               BIT_DStream_endOfBuffer = 1,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   132
               BIT_DStream_completed = 2,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   133
               BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   134
               /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   135
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   136
MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   137
MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   138
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   139
MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   140
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   141
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   142
/* Start by invoking BIT_initDStream().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   143
*  A chunk of the bitStream is then stored into a local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   144
*  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   145
*  You can then retrieve bitFields stored into the local register, **in reverse order**.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   146
*  Local register is explicitly reloaded from memory by the BIT_reloadDStream() method.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   147
*  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BIT_DStream_unfinished.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   148
*  Otherwise, it can be less than that, so proceed accordingly.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   149
*  Checking if DStream has reached its end can be performed with BIT_endOfDStream().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   150
*/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   151
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   152
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   153
/*-****************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   154
*  unsafe API
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   155
******************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   156
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC, size_t value, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   157
/* faster, but works only if value is "clean", meaning all high bits above nbBits are 0 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   158
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   159
MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   160
/* unsafe version; does not check buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   161
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   162
MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   163
/* faster, but works only if nbBits >= 1 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   164
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   165
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   166
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   167
/*-**************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   168
*  Internal functions
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   169
****************************************************************/
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   170
MEM_STATIC unsigned BIT_highbit32 (U32 val)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   171
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   172
    assert(val != 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   173
    {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   174
#   if defined(_MSC_VER)   /* Visual */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   175
        unsigned long r=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   176
        _BitScanReverse ( &r, val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   177
        return (unsigned) r;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   178
#   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   179
        return 31 - __builtin_clz (val);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   180
#   else   /* Software version */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   181
        static const unsigned DeBruijnClz[32] = { 0,  9,  1, 10, 13, 21,  2, 29,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   182
                                                 11, 14, 16, 18, 22, 25,  3, 30,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   183
                                                  8, 12, 20, 28, 15, 17, 24,  7,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   184
                                                 19, 27, 23,  6, 26,  5,  4, 31 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   185
        U32 v = val;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   186
        v |= v >> 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   187
        v |= v >> 2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   188
        v |= v >> 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   189
        v |= v >> 8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   190
        v |= v >> 16;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   191
        return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   192
#   endif
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   193
    }
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   194
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   195
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   196
/*=====    Local Constants   =====*/
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   197
static const unsigned BIT_mask[] = {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   198
    0,          1,         3,         7,         0xF,       0x1F,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   199
    0x3F,       0x7F,      0xFF,      0x1FF,     0x3FF,     0x7FF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   200
    0xFFF,      0x1FFF,    0x3FFF,    0x7FFF,    0xFFFF,    0x1FFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   201
    0x3FFFF,    0x7FFFF,   0xFFFFF,   0x1FFFFF,  0x3FFFFF,  0x7FFFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   202
    0xFFFFFF,   0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   203
    0x3FFFFFFF, 0x7FFFFFFF}; /* up to 31 bits */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   204
#define BIT_MASK_SIZE (sizeof(BIT_mask) / sizeof(BIT_mask[0]))
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   205
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   206
/*-**************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   207
*  bitStream encoding
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   208
****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   209
/*! BIT_initCStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   210
 *  `dstCapacity` must be > sizeof(size_t)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   211
 *  @return : 0 if success,
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   212
 *            otherwise an error code (can be tested using ERR_isError()) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   213
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   214
                                  void* startPtr, size_t dstCapacity)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   215
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   216
    bitC->bitContainer = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   217
    bitC->bitPos = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   218
    bitC->startPtr = (char*)startPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   219
    bitC->ptr = bitC->startPtr;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   220
    bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->bitContainer);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   221
    if (dstCapacity <= sizeof(bitC->bitContainer)) return ERROR(dstSize_tooSmall);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   222
    return 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   223
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   224
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   225
/*! BIT_addBits() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   226
 *  can add up to 31 bits into `bitC`.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   227
 *  Note : does not check for register overflow ! */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   228
MEM_STATIC void BIT_addBits(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   229
                            size_t value, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   230
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   231
    MEM_STATIC_ASSERT(BIT_MASK_SIZE == 32);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   232
    assert(nbBits < BIT_MASK_SIZE);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   233
    assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   234
    bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   235
    bitC->bitPos += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   236
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   237
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   238
/*! BIT_addBitsFast() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   239
 *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   240
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t* bitC,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   241
                                size_t value, unsigned nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   242
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   243
    assert((value>>nbBits) == 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   244
    assert(nbBits + bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   245
    bitC->bitContainer |= value << bitC->bitPos;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   246
    bitC->bitPos += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   247
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   248
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   249
/*! BIT_flushBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   250
 *  assumption : bitContainer has not overflowed
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   251
 *  unsafe version; does not check buffer overflow */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   252
MEM_STATIC void BIT_flushBitsFast(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   253
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   254
    size_t const nbBytes = bitC->bitPos >> 3;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   255
    assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   256
    MEM_writeLEST(bitC->ptr, bitC->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   257
    bitC->ptr += nbBytes;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   258
    assert(bitC->ptr <= bitC->endPtr);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   259
    bitC->bitPos &= 7;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   260
    bitC->bitContainer >>= nbBytes*8;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   261
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   262
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   263
/*! BIT_flushBits() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   264
 *  assumption : bitContainer has not overflowed
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   265
 *  safe version; check for buffer overflow, and prevents it.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   266
 *  note : does not signal buffer overflow.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   267
 *  overflow will be revealed later on using BIT_closeCStream() */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   268
MEM_STATIC void BIT_flushBits(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   269
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   270
    size_t const nbBytes = bitC->bitPos >> 3;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   271
    assert(bitC->bitPos < sizeof(bitC->bitContainer) * 8);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   272
    MEM_writeLEST(bitC->ptr, bitC->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   273
    bitC->ptr += nbBytes;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   274
    if (bitC->ptr > bitC->endPtr) bitC->ptr = bitC->endPtr;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   275
    bitC->bitPos &= 7;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   276
    bitC->bitContainer >>= nbBytes*8;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   277
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   278
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   279
/*! BIT_closeCStream() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   280
 *  @return : size of CStream, in bytes,
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   281
 *            or 0 if it could not fit into dstBuffer */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   282
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t* bitC)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   283
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   284
    BIT_addBitsFast(bitC, 1, 1);   /* endMark */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   285
    BIT_flushBits(bitC);
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   286
    if (bitC->ptr >= bitC->endPtr) return 0; /* overflow detected */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   287
    return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   288
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   289
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   290
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   291
/*-********************************************************
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   292
*  bitStream decoding
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   293
**********************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   294
/*! BIT_initDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   295
 *  Initialize a BIT_DStream_t.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   296
 * `bitD` : a pointer to an already allocated BIT_DStream_t structure.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   297
 * `srcSize` must be the *exact* size of the bitStream, in bytes.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   298
 * @return : size of stream (== srcSize), or an errorCode if a problem is detected
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   299
 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   300
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   301
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   302
    if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   303
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   304
    bitD->start = (const char*)srcBuffer;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   305
    bitD->limitPtr = bitD->start + sizeof(bitD->bitContainer);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   306
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   307
    if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   308
        bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   309
        bitD->bitContainer = MEM_readLEST(bitD->ptr);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   310
        { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
   311
          bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;  /* ensures bitsConsumed is always set */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   312
          if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   313
    } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   314
        bitD->ptr   = bitD->start;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   315
        bitD->bitContainer = *(const BYTE*)(bitD->start);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   316
        switch(srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   317
        {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   318
        case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   319
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   320
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   321
        case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   322
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   323
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   324
        case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   325
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   326
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   327
        case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   328
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   329
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   330
        case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   331
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   332
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   333
        case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   334
                /* fall-through */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   335
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   336
        default: break;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   337
        }
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   338
        {   BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   339
            bitD->bitsConsumed = lastByte ? 8 - BIT_highbit32(lastByte) : 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   340
            if (lastByte == 0) return ERROR(corruption_detected);  /* endMark not present */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   341
        }
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   342
        bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   343
    }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   344
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   345
    return srcSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   346
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   347
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   348
MEM_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   349
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   350
    return bitContainer >> start;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   351
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   352
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   353
MEM_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 const nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   354
{
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
   355
#if defined(__BMI__) && defined(__GNUC__) && __GNUC__*1000+__GNUC_MINOR__ >= 4008  /* experimental */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   356
#  if defined(__x86_64__)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   357
    if (sizeof(bitContainer)==8)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   358
        return _bextr_u64(bitContainer, start, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   359
    else
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   360
#  endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   361
        return _bextr_u32(bitContainer, start, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   362
#else
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   363
    assert(nbBits < BIT_MASK_SIZE);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   364
    return (bitContainer >> start) & BIT_mask[nbBits];
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   365
#endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   366
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   367
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   368
MEM_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   369
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   370
    assert(nbBits < BIT_MASK_SIZE);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   371
    return bitContainer & BIT_mask[nbBits];
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   372
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   373
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   374
/*! BIT_lookBits() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   375
 *  Provides next n bits from local register.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   376
 *  local register is not modified.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   377
 *  On 32-bits, maxNbBits==24.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   378
 *  On 64-bits, maxNbBits==56.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   379
 * @return : value extracted */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   380
MEM_STATIC size_t BIT_lookBits(const BIT_DStream_t* bitD, U32 nbBits)
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   381
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   382
#if defined(__BMI__) && defined(__GNUC__)   /* experimental; fails if bitD->bitsConsumed + nbBits > sizeof(bitD->bitContainer)*8 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   383
    return BIT_getMiddleBits(bitD->bitContainer, (sizeof(bitD->bitContainer)*8) - bitD->bitsConsumed - nbBits, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   384
#else
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   385
    U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   386
    return ((bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> 1) >> ((regMask-nbBits) & regMask);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   387
#endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   388
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   389
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   390
/*! BIT_lookBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   391
 *  unsafe version; only works if nbBits >= 1 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   392
MEM_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   393
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   394
    U32 const regMask = sizeof(bitD->bitContainer)*8 - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   395
    assert(nbBits >= 1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   396
    return (bitD->bitContainer << (bitD->bitsConsumed & regMask)) >> (((regMask+1)-nbBits) & regMask);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   397
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   398
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   399
MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   400
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   401
    bitD->bitsConsumed += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   402
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   403
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   404
/*! BIT_readBits() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   405
 *  Read (consume) next n bits from local register and update.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   406
 *  Pay attention to not read more than nbBits contained into local register.
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   407
 * @return : extracted value. */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   408
MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   409
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   410
    size_t const value = BIT_lookBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   411
    BIT_skipBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   412
    return value;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   413
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   414
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   415
/*! BIT_readBitsFast() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   416
 *  unsafe version; only works only if nbBits >= 1 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   417
MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   418
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   419
    size_t const value = BIT_lookBitsFast(bitD, nbBits);
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   420
    assert(nbBits >= 1);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   421
    BIT_skipBits(bitD, nbBits);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   422
    return value;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   423
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   424
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   425
/*! BIT_reloadDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   426
 *  Refill `bitD` from buffer previously set in BIT_initDStream() .
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   427
 *  This function is safe, it guarantees it will not read beyond src buffer.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   428
 * @return : status of `BIT_DStream_t` internal register.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   429
 *           when status == BIT_DStream_unfinished, internal register is filled with at least 25 or 57 bits */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   430
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   431
{
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   432
    if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* overflow detected, like end of stream */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   433
        return BIT_DStream_overflow;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   434
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   435
    if (bitD->ptr >= bitD->limitPtr) {
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   436
        bitD->ptr -= bitD->bitsConsumed >> 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   437
        bitD->bitsConsumed &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   438
        bitD->bitContainer = MEM_readLEST(bitD->ptr);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   439
        return BIT_DStream_unfinished;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   440
    }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   441
    if (bitD->ptr == bitD->start) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   442
        if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   443
        return BIT_DStream_completed;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   444
    }
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   445
    /* start < ptr < limitPtr */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   446
    {   U32 nbBytes = bitD->bitsConsumed >> 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   447
        BIT_DStream_status result = BIT_DStream_unfinished;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   448
        if (bitD->ptr - nbBytes < bitD->start) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   449
            nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   450
            result = BIT_DStream_endOfBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   451
        }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   452
        bitD->ptr -= nbBytes;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   453
        bitD->bitsConsumed -= nbBytes*8;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   454
        bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD->bitContainer), otherwise bitD->ptr == bitD->start */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   455
        return result;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   456
    }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   457
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   458
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   459
/*! BIT_endOfDStream() :
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   460
 * @return : 1 if DStream has _exactly_ reached its end (all bits consumed).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
   461
 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   462
MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   463
{
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   464
    return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   465
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   466
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   467
#if defined (__cplusplus)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   468
}
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   469
#endif
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   470
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
   471
#endif /* BITSTREAM_H_MODULE */