1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lz_decoder.h 4207753Smm/// \brief LZ out window 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#ifndef LZMA_LZ_DECODER_H 15207753Smm#define LZMA_LZ_DECODER_H 16207753Smm 17207753Smm#include "common.h" 18207753Smm 19207753Smm 20207753Smmtypedef struct { 21207753Smm /// Pointer to the dictionary buffer. It can be an allocated buffer 22207753Smm /// internal to liblzma, or it can a be a buffer given by the 23207753Smm /// application when in single-call mode (not implemented yet). 24207753Smm uint8_t *buf; 25207753Smm 26207753Smm /// Write position in dictionary. The next byte will be written to 27207753Smm /// buf[pos]. 28207753Smm size_t pos; 29207753Smm 30207753Smm /// Indicates how full the dictionary is. This is used by 31207753Smm /// dict_is_distance_valid() to detect corrupt files that would 32207753Smm /// read beyond the beginning of the dictionary. 33207753Smm size_t full; 34207753Smm 35207753Smm /// Write limit 36207753Smm size_t limit; 37207753Smm 38207753Smm /// Size of the dictionary 39207753Smm size_t size; 40207753Smm 41207753Smm /// True when dictionary should be reset before decoding more data. 42207753Smm bool need_reset; 43207753Smm 44207753Smm} lzma_dict; 45207753Smm 46207753Smm 47207753Smmtypedef struct { 48207753Smm size_t dict_size; 49207753Smm const uint8_t *preset_dict; 50207753Smm size_t preset_dict_size; 51207753Smm} lzma_lz_options; 52207753Smm 53207753Smm 54207753Smmtypedef struct { 55207753Smm /// Data specific to the LZ-based decoder 56207753Smm lzma_coder *coder; 57207753Smm 58207753Smm /// Function to decode from in[] to *dict 59207753Smm lzma_ret (*code)(lzma_coder *restrict coder, 60207753Smm lzma_dict *restrict dict, const uint8_t *restrict in, 61207753Smm size_t *restrict in_pos, size_t in_size); 62207753Smm 63207753Smm void (*reset)(lzma_coder *coder, const void *options); 64207753Smm 65207753Smm /// Set the uncompressed size 66207753Smm void (*set_uncompressed)(lzma_coder *coder, 67207753Smm lzma_vli uncompressed_size); 68207753Smm 69207753Smm /// Free allocated resources 70207753Smm void (*end)(lzma_coder *coder, lzma_allocator *allocator); 71207753Smm 72207753Smm} lzma_lz_decoder; 73207753Smm 74207753Smm 75207753Smm#define LZMA_LZ_DECODER_INIT \ 76207753Smm (lzma_lz_decoder){ \ 77207753Smm .coder = NULL, \ 78207753Smm .code = NULL, \ 79207753Smm .reset = NULL, \ 80207753Smm .set_uncompressed = NULL, \ 81207753Smm .end = NULL, \ 82207753Smm } 83207753Smm 84207753Smm 85207753Smmextern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next, 86207753Smm lzma_allocator *allocator, const lzma_filter_info *filters, 87207753Smm lzma_ret (*lz_init)(lzma_lz_decoder *lz, 88207753Smm lzma_allocator *allocator, const void *options, 89207753Smm lzma_lz_options *lz_options)); 90207753Smm 91207753Smmextern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size); 92207753Smm 93207753Smmextern void lzma_lz_decoder_uncompressed( 94207753Smm lzma_coder *coder, lzma_vli uncompressed_size); 95207753Smm 96207753Smm 97207753Smm////////////////////// 98207753Smm// Inline functions // 99207753Smm////////////////////// 100207753Smm 101207753Smm/// Get a byte from the history buffer. 102207753Smmstatic inline uint8_t 103207753Smmdict_get(const lzma_dict *const dict, const uint32_t distance) 104207753Smm{ 105207753Smm return dict->buf[dict->pos - distance - 1 106207753Smm + (distance < dict->pos ? 0 : dict->size)]; 107207753Smm} 108207753Smm 109207753Smm 110207753Smm/// Test if dictionary is empty. 111207753Smmstatic inline bool 112207753Smmdict_is_empty(const lzma_dict *const dict) 113207753Smm{ 114207753Smm return dict->full == 0; 115207753Smm} 116207753Smm 117207753Smm 118207753Smm/// Validate the match distance 119207753Smmstatic inline bool 120207753Smmdict_is_distance_valid(const lzma_dict *const dict, const size_t distance) 121207753Smm{ 122207753Smm return dict->full > distance; 123207753Smm} 124207753Smm 125207753Smm 126207753Smm/// Repeat *len bytes at distance. 127207753Smmstatic inline bool 128207753Smmdict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len) 129207753Smm{ 130207753Smm // Don't write past the end of the dictionary. 131207753Smm const size_t dict_avail = dict->limit - dict->pos; 132213700Smm uint32_t left = my_min(dict_avail, *len); 133207753Smm *len -= left; 134207753Smm 135207753Smm // Repeat a block of data from the history. Because memcpy() is faster 136207753Smm // than copying byte by byte in a loop, the copying process gets split 137207753Smm // into three cases. 138207753Smm if (distance < left) { 139207753Smm // Source and target areas overlap, thus we can't use 140207753Smm // memcpy() nor even memmove() safely. 141207753Smm do { 142207753Smm dict->buf[dict->pos] = dict_get(dict, distance); 143207753Smm ++dict->pos; 144207753Smm } while (--left > 0); 145207753Smm 146207753Smm } else if (distance < dict->pos) { 147207753Smm // The easiest and fastest case 148207753Smm memcpy(dict->buf + dict->pos, 149207753Smm dict->buf + dict->pos - distance - 1, 150207753Smm left); 151207753Smm dict->pos += left; 152207753Smm 153207753Smm } else { 154207753Smm // The bigger the dictionary, the more rare this 155207753Smm // case occurs. We need to "wrap" the dict, thus 156207753Smm // we might need two memcpy() to copy all the data. 157207753Smm assert(dict->full == dict->size); 158207753Smm const uint32_t copy_pos 159207753Smm = dict->pos - distance - 1 + dict->size; 160207753Smm uint32_t copy_size = dict->size - copy_pos; 161207753Smm 162207753Smm if (copy_size < left) { 163207753Smm memmove(dict->buf + dict->pos, dict->buf + copy_pos, 164207753Smm copy_size); 165207753Smm dict->pos += copy_size; 166207753Smm copy_size = left - copy_size; 167207753Smm memcpy(dict->buf + dict->pos, dict->buf, copy_size); 168207753Smm dict->pos += copy_size; 169207753Smm } else { 170207753Smm memmove(dict->buf + dict->pos, dict->buf + copy_pos, 171207753Smm left); 172207753Smm dict->pos += left; 173207753Smm } 174207753Smm } 175207753Smm 176207753Smm // Update how full the dictionary is. 177207753Smm if (dict->full < dict->pos) 178207753Smm dict->full = dict->pos; 179207753Smm 180207753Smm return unlikely(*len != 0); 181207753Smm} 182207753Smm 183207753Smm 184207753Smm/// Puts one byte into the dictionary. Returns true if the dictionary was 185207753Smm/// already full and the byte couldn't be added. 186207753Smmstatic inline bool 187207753Smmdict_put(lzma_dict *dict, uint8_t byte) 188207753Smm{ 189207753Smm if (unlikely(dict->pos == dict->limit)) 190207753Smm return true; 191207753Smm 192207753Smm dict->buf[dict->pos++] = byte; 193207753Smm 194207753Smm if (dict->pos > dict->full) 195207753Smm dict->full = dict->pos; 196207753Smm 197207753Smm return false; 198207753Smm} 199207753Smm 200207753Smm 201207753Smm/// Copies arbitrary amount of data into the dictionary. 202207753Smmstatic inline void 203207753Smmdict_write(lzma_dict *restrict dict, const uint8_t *restrict in, 204207753Smm size_t *restrict in_pos, size_t in_size, 205207753Smm size_t *restrict left) 206207753Smm{ 207207753Smm // NOTE: If we are being given more data than the size of the 208207753Smm // dictionary, it could be possible to optimize the LZ decoder 209207753Smm // so that not everything needs to go through the dictionary. 210207753Smm // This shouldn't be very common thing in practice though, and 211207753Smm // the slowdown of one extra memcpy() isn't bad compared to how 212207753Smm // much time it would have taken if the data were compressed. 213207753Smm 214207753Smm if (in_size - *in_pos > *left) 215207753Smm in_size = *in_pos + *left; 216207753Smm 217207753Smm *left -= lzma_bufcpy(in, in_pos, in_size, 218207753Smm dict->buf, &dict->pos, dict->limit); 219207753Smm 220207753Smm if (dict->pos > dict->full) 221207753Smm dict->full = dict->pos; 222207753Smm 223207753Smm return; 224207753Smm} 225207753Smm 226207753Smm 227207753Smmstatic inline void 228207753Smmdict_reset(lzma_dict *dict) 229207753Smm{ 230207753Smm dict->need_reset = true; 231207753Smm return; 232207753Smm} 233207753Smm 234207753Smm#endif 235