1 /////////////////////////////////////////////////////////////////////////////// 2 // 3 /// \file lz_decoder.h 4 /// \brief LZ out window 5 /// 6 // Authors: Igor Pavlov 7 // Lasse Collin 8 // 9 // This file has been put into the public domain. 10 // You can do whatever you want with this file. 11 // 12 /////////////////////////////////////////////////////////////////////////////// 13 14 #ifndef LZMA_LZ_DECODER_H 15 #define LZMA_LZ_DECODER_H 16 17 #include "common.h" 18 19 20 typedef struct { 21 /// Pointer to the dictionary buffer. It can be an allocated buffer 22 /// internal to liblzma, or it can a be a buffer given by the 23 /// application when in single-call mode (not implemented yet). 24 uint8_t *buf; 25 26 /// Write position in dictionary. The next byte will be written to 27 /// buf[pos]. 28 size_t pos; 29 30 /// Indicates how full the dictionary is. This is used by 31 /// dict_is_distance_valid() to detect corrupt files that would 32 /// read beyond the beginning of the dictionary. 33 size_t full; 34 35 /// Write limit 36 size_t limit; 37 38 /// Size of the dictionary 39 size_t size; 40 41 /// True when dictionary should be reset before decoding more data. 42 bool need_reset; 43 44 } lzma_dict; 45 46 47 typedef struct { 48 size_t dict_size; 49 const uint8_t *preset_dict; 50 size_t preset_dict_size; 51 } lzma_lz_options; 52 53 54 typedef struct { 55 /// Data specific to the LZ-based decoder 56 void *coder; 57 58 /// Function to decode from in[] to *dict 59 lzma_ret (*code)(void *coder, 60 lzma_dict *restrict dict, const uint8_t *restrict in, 61 size_t *restrict in_pos, size_t in_size); 62 63 void (*reset)(void *coder, const void *options); 64 65 /// Set the uncompressed size. If uncompressed_size == LZMA_VLI_UNKNOWN 66 /// then allow_eopm will always be true. 67 void (*set_uncompressed)(void *coder, lzma_vli uncompressed_size, 68 bool allow_eopm); 69 70 /// Free allocated resources 71 void (*end)(void *coder, const lzma_allocator *allocator); 72 73 } lzma_lz_decoder; 74 75 76 #define LZMA_LZ_DECODER_INIT \ 77 (lzma_lz_decoder){ \ 78 .coder = NULL, \ 79 .code = NULL, \ 80 .reset = NULL, \ 81 .set_uncompressed = NULL, \ 82 .end = NULL, \ 83 } 84 85 86 extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next, 87 const lzma_allocator *allocator, 88 const lzma_filter_info *filters, 89 lzma_ret (*lz_init)(lzma_lz_decoder *lz, 90 const lzma_allocator *allocator, const void *options, 91 lzma_lz_options *lz_options)); 92 93 extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size); 94 95 extern void lzma_lz_decoder_uncompressed( 96 void *coder, lzma_vli uncompressed_size, bool allow_eopm); 97 98 99 ////////////////////// 100 // Inline functions // 101 ////////////////////// 102 103 /// Get a byte from the history buffer. 104 static inline uint8_t 105 dict_get(const lzma_dict *const dict, const uint32_t distance) 106 { 107 return dict->buf[dict->pos - distance - 1 108 + (distance < dict->pos ? 0 : dict->size)]; 109 } 110 111 112 /// Test if dictionary is empty. 113 static inline bool 114 dict_is_empty(const lzma_dict *const dict) 115 { 116 return dict->full == 0; 117 } 118 119 120 /// Validate the match distance 121 static inline bool 122 dict_is_distance_valid(const lzma_dict *const dict, const size_t distance) 123 { 124 return dict->full > distance; 125 } 126 127 128 /// Repeat *len bytes at distance. 129 static inline bool 130 dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len) 131 { 132 // Don't write past the end of the dictionary. 133 const size_t dict_avail = dict->limit - dict->pos; 134 uint32_t left = my_min(dict_avail, *len); 135 *len -= left; 136 137 // Repeat a block of data from the history. Because memcpy() is faster 138 // than copying byte by byte in a loop, the copying process gets split 139 // into three cases. 140 if (distance < left) { 141 // Source and target areas overlap, thus we can't use 142 // memcpy() nor even memmove() safely. 143 do { 144 dict->buf[dict->pos] = dict_get(dict, distance); 145 ++dict->pos; 146 } while (--left > 0); 147 148 } else if (distance < dict->pos) { 149 // The easiest and fastest case 150 memcpy(dict->buf + dict->pos, 151 dict->buf + dict->pos - distance - 1, 152 left); 153 dict->pos += left; 154 155 } else { 156 // The bigger the dictionary, the more rare this 157 // case occurs. We need to "wrap" the dict, thus 158 // we might need two memcpy() to copy all the data. 159 assert(dict->full == dict->size); 160 const uint32_t copy_pos 161 = dict->pos - distance - 1 + dict->size; 162 uint32_t copy_size = dict->size - copy_pos; 163 164 if (copy_size < left) { 165 memmove(dict->buf + dict->pos, dict->buf + copy_pos, 166 copy_size); 167 dict->pos += copy_size; 168 copy_size = left - copy_size; 169 memcpy(dict->buf + dict->pos, dict->buf, copy_size); 170 dict->pos += copy_size; 171 } else { 172 memmove(dict->buf + dict->pos, dict->buf + copy_pos, 173 left); 174 dict->pos += left; 175 } 176 } 177 178 // Update how full the dictionary is. 179 if (dict->full < dict->pos) 180 dict->full = dict->pos; 181 182 return unlikely(*len != 0); 183 } 184 185 186 /// Puts one byte into the dictionary. Returns true if the dictionary was 187 /// already full and the byte couldn't be added. 188 static inline bool 189 dict_put(lzma_dict *dict, uint8_t byte) 190 { 191 if (unlikely(dict->pos == dict->limit)) 192 return true; 193 194 dict->buf[dict->pos++] = byte; 195 196 if (dict->pos > dict->full) 197 dict->full = dict->pos; 198 199 return false; 200 } 201 202 203 /// Copies arbitrary amount of data into the dictionary. 204 static inline void 205 dict_write(lzma_dict *restrict dict, const uint8_t *restrict in, 206 size_t *restrict in_pos, size_t in_size, 207 size_t *restrict left) 208 { 209 // NOTE: If we are being given more data than the size of the 210 // dictionary, it could be possible to optimize the LZ decoder 211 // so that not everything needs to go through the dictionary. 212 // This shouldn't be very common thing in practice though, and 213 // the slowdown of one extra memcpy() isn't bad compared to how 214 // much time it would have taken if the data were compressed. 215 216 if (in_size - *in_pos > *left) 217 in_size = *in_pos + *left; 218 219 *left -= lzma_bufcpy(in, in_pos, in_size, 220 dict->buf, &dict->pos, dict->limit); 221 222 if (dict->pos > dict->full) 223 dict->full = dict->pos; 224 225 return; 226 } 227 228 229 static inline void 230 dict_reset(lzma_dict *dict) 231 { 232 dict->need_reset = true; 233 return; 234 } 235 236 #endif 237