ceph/src/isa-l/igzip/huffman.h

   1 /**********************************************************************
   2   Copyright(c) 2011-2016 Intel Corporation All rights reserved.
   3
   4   Redistribution and use in source and binary forms, with or without
   5   modification, are permitted provided that the following conditions
   6   are met:
   7     * Redistributions of source code must retain the above copyright
   8       notice, this list of conditions and the following disclaimer.
   9     * Redistributions in binary form must reproduce the above copyright
  10       notice, this list of conditions and the following disclaimer in
  11       the documentation and/or other materials provided with the
  12       distribution.
  13     * Neither the name of Intel Corporation nor the names of its
  14       contributors may be used to endorse or promote products derived
  15       from this software without specific prior written permission.
  16
  17   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 **********************************************************************/
  29
  30 #include <stdint.h>
  31 #include <stdlib.h>
  32 #include <assert.h>
  33 #include "igzip_lib.h"
  34
  35 #ifdef _MSC_VER
  36 # include <intrin.h>
  37 # define inline __inline
  38 #else
  39 # include <x86intrin.h>
  40 #endif
  41
  42 #ifndef IGZIP_USE_GZIP_FORMAT
  43 # define DEFLATE 1
  44 #endif
  45
  46
  47 extern uint32_t  CrcTable[256];
  48
  49 static inline uint32_t bsr(uint32_t val)
  50 {
  51         uint32_t msb;
  52 #ifdef __LZCNT__
  53         msb = 16 - __lzcnt16(val);
  54 #else
  55         for(msb = 0; val > 0; val >>= 1)
  56                 msb++;
  57 #endif
  58         return msb;
  59 }
  60
  61 static inline uint32_t tzcnt(uint64_t val)
  62 {
  63         uint32_t cnt;
  64
  65 #ifdef __x86_64__
  66
  67         cnt = __builtin_ctzll(val) / 8;//__tzcnt_u64(val);
  68
  69 #else
  70         for(cnt = 8; val > 0; val <<= 8)
  71                 cnt -= 1;
  72 #endif
  73         return cnt;
  74 }
  75
  76 static void compute_dist_code(struct isal_hufftables *hufftables, uint16_t dist, uint64_t *p_code, uint64_t *p_len)
  77 {
  78         assert(dist > DIST_TABLE_SIZE);
  79
  80         dist -= 1;
  81         uint32_t msb;
  82         uint32_t num_extra_bits;
  83         uint32_t extra_bits;
  84         uint32_t sym;
  85         uint32_t len;
  86         uint32_t code;
  87
  88         msb = bsr(dist);
  89         assert(msb >= 1);
  90         num_extra_bits = msb - 2;
  91         extra_bits = dist & ((1 << num_extra_bits) - 1);
  92         dist >>= num_extra_bits;
  93         sym = dist + 2 * num_extra_bits;
  94         assert(sym < 30);
  95         code = hufftables->dcodes[sym - DECODE_OFFSET];
  96         len = hufftables->dcodes_sizes[sym - DECODE_OFFSET];
  97         *p_code = code | (extra_bits << len);
  98         *p_len = len + num_extra_bits;
  99 }
 100
 101 static inline void get_dist_code(struct isal_hufftables *hufftables, uint32_t dist, uint64_t *code, uint64_t *len)
 102 {
 103         if (dist < 1)
 104                 dist = 0;
 105         assert(dist >= 1);
 106         assert(dist <= 32768);
 107         if (dist <= DIST_TABLE_SIZE) {
 108                 uint64_t code_len;
 109                 code_len = hufftables->dist_table[dist - 1];
 110                 *code = code_len >> 5;
 111                 *len = code_len & 0x1F;
 112         } else {
 113                 compute_dist_code(hufftables, dist, code, len);
 114         }
 115 }
 116
 117 static inline void get_len_code(struct isal_hufftables *hufftables, uint32_t length, uint64_t *code, uint64_t *len)
 118 {
 119         assert(length >= 3);
 120         assert(length <= 258);
 121
 122         uint64_t code_len;
 123         code_len = hufftables->len_table[length - 3];
 124         *code = code_len >> 5;
 125         *len = code_len & 0x1F;
 126 }
 127
 128 static inline void get_lit_code(struct isal_hufftables *hufftables, uint32_t lit, uint64_t *code, uint64_t *len)
 129 {
 130         assert(lit <= 256);
 131
 132         *code = hufftables->lit_table[lit];
 133         *len = hufftables->lit_table_sizes[lit];
 134 }
 135
 136 /**
 137  * @brief Returns a hash of the first 3 bytes of input data.
 138  */
 139 static inline uint32_t compute_hash(uint32_t data)
 140 {
 141         data &= 0x00FFFFFF;
 142 #ifdef __SSE4_1__
 143
 144         return _mm_crc32_u32(0, data);
 145
 146 #else
 147         /* Use multiplication to create a hash, 0xBDD06057 is a prime number */
 148         return ((uint64_t)data * 0xB2D06057) >> 16;
 149
 150 #endif /* __SSE4_1__ */
 151 }
 152
 153
 154 /**
 155  * @brief Returns how long str1 and str2 have the same symbols.
 156  * @param str1: First input string.
 157  * @param str2: Second input string.
 158  * @param max_length: length of the smaller string.
 159  */
 160 static inline int compare258(uint8_t * str1, uint8_t * str2, uint32_t max_length)
 161 {
 162         uint32_t count;
 163         uint64_t test;
 164         uint64_t loop_length;
 165
 166         if(max_length > 258)
 167                 max_length = 258;
 168
 169         loop_length = max_length & ~0x7;
 170
 171         for(count = 0; count < loop_length; count += 8){
 172                 test = *(uint64_t *) str1;
 173                 test ^= *(uint64_t *) str2;
 174                 if(test != 0)
 175                         return count + tzcnt(test);
 176                 str1 += 8;
 177                 str2 += 8;
 178         }
 179
 180         switch(max_length % 8){
 181
 182         case 7:
 183                 if(*str1++ != *str2++)
 184                         return count;
 185                 count++;
 186         case 6:
 187                 if(*str1++ != *str2++)
 188                         return count;
 189                 count++;
 190         case 5:
 191                 if(*str1++ != *str2++)
 192                         return count;
 193                 count++;
 194         case 4:
 195                 if(*str1++ != *str2++)
 196                         return count;
 197                 count++;
 198         case 3:
 199                 if(*str1++ != *str2++)
 200                         return count;
 201                 count++;
 202         case 2:
 203                 if(*str1++ != *str2++)
 204                         return count;
 205                 count++;
 206         case 1:
 207                 if(*str1 != *str2)
 208                         return count;
 209                 count++;
 210         }
 211
 212         return count;
 213 }
 214
 215 static inline void update_crc(uint32_t* crc, uint8_t * start, uint32_t length)
 216 {
 217 #ifndef DEFLATE
 218         uint8_t *end = start + length;
 219
 220         while (start < end)
 221                 *crc = (*crc >> 8) ^ CrcTable[(*crc & 0x000000FF) ^ *start++];
 222 #else
 223         return;
 224 #endif
 225 }
 226