Lines Matching refs:s
157 /* If 1, it's a match. Otherwise it's a single 8-bit literal. */
160 /* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
447 * has been allocated by us in this file; it's not
603 static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s)
605 uint32_t prev_byte = dict_get(&s->dict, 0);
606 uint32_t low = prev_byte >> (8 - s->lzma.lc);
607 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc;
608 return s->lzma.literal[low + high];
612 static void lzma_literal(struct xz_dec_lzma2 *s)
621 probs = lzma_literal_probs(s);
623 if (lzma_state_is_literal(s->lzma.state)) {
624 symbol = rc_bittree(&s->rc, probs, 0x100);
627 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1;
635 if (rc_bit(&s->rc, &probs[i])) {
645 dict_put(&s->dict, (uint8_t)symbol);
646 lzma_state_literal(&s->lzma.state);
649 /* Decode the length of the match into s->lzma.len. */
650 static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l,
656 if (!rc_bit(&s->rc, &l->choice)) {
659 s->lzma.len = MATCH_LEN_MIN;
661 if (!rc_bit(&s->rc, &l->choice2)) {
664 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS;
668 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS
673 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit;
676 /* Decode a match. The distance will be stored in s->lzma.rep0. */
677 static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
683 lzma_state_match(&s->lzma.state);
685 s->lzma.rep3 = s->lzma.rep2;
686 s->lzma.rep2 = s->lzma.rep1;
687 s->lzma.rep1 = s->lzma.rep0;
689 lzma_len(s, &s->lzma.match_len_dec, pos_state);
691 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)];
692 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS;
695 s->lzma.rep0 = dist_slot;
698 s->lzma.rep0 = 2 + (dist_slot & 1);
701 s->lzma.rep0 <<= limit;
702 probs = s->lzma.dist_special + s->lzma.rep0
704 rc_bittree_reverse(&s->rc, probs,
705 &s->lzma.rep0, limit);
707 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS);
708 s->lzma.rep0 <<= ALIGN_BITS;
709 rc_bittree_reverse(&s->rc, s->lzma.dist_align,
710 &s->lzma.rep0, ALIGN_BITS);
717 * seen matches. The distance will be stored in s->lzma.rep0.
719 static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state)
723 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) {
724 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[
725 s->lzma.state][pos_state])) {
726 lzma_state_short_rep(&s->lzma.state);
727 s->lzma.len = 1;
731 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) {
732 tmp = s->lzma.rep1;
734 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) {
735 tmp = s->lzma.rep2;
737 tmp = s->lzma.rep3;
738 s->lzma.rep3 = s->lzma.rep2;
741 s->lzma.rep2 = s->lzma.rep1;
744 s->lzma.rep1 = s->lzma.rep0;
745 s->lzma.rep0 = tmp;
748 lzma_state_long_rep(&s->lzma.state);
749 lzma_len(s, &s->lzma.rep_len_dec, pos_state);
753 static bool lzma_main(struct xz_dec_lzma2 *s)
761 if (dict_has_space(&s->dict) && s->lzma.len > 0)
762 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0);
768 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) {
769 pos_state = s->dict.pos & s->lzma.pos_mask;
771 if (!rc_bit(&s->rc, &s->lzma.is_match[
772 s->lzma.state][pos_state])) {
773 lzma_literal(s);
775 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state]))
776 lzma_rep_match(s, pos_state);
778 lzma_match(s, pos_state);
780 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0))
789 rc_normalize(&s->rc);
798 static void lzma_reset(struct xz_dec_lzma2 *s)
803 s->lzma.state = STATE_LIT_LIT;
804 s->lzma.rep0 = 0;
805 s->lzma.rep1 = 0;
806 s->lzma.rep2 = 0;
807 s->lzma.rep3 = 0;
808 s->lzma.len = 0;
819 probs = s->lzma.is_match[0];
823 rc_reset(&s->rc);
831 static bool lzma_props(struct xz_dec_lzma2 *s, uint8_t props)
836 s->lzma.pos_mask = 0;
839 ++s->lzma.pos_mask;
842 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1;
844 s->lzma.literal_pos_mask = 0;
847 ++s->lzma.literal_pos_mask;
850 s->lzma.lc = props;
852 if (s->lzma.lc + s->lzma.literal_pos_mask > 4)
855 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1;
857 lzma_reset(s);
867 * The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
869 * wrapper function takes care of making the LZMA decoder's assumption safe.
873 * there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
874 * s->temp.buf, which (hopefully) gets filled on the next call to this
878 static bool lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b)
884 if (s->temp.size > 0 || s->lzma2.compressed == 0) {
885 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size;
886 if (tmp > s->lzma2.compressed - s->temp.size)
887 tmp = s->lzma2.compressed - s->temp.size;
891 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp);
893 if (s->temp.size + tmp == s->lzma2.compressed) {
894 memzero(s->temp.buf + s->temp.size + tmp,
895 sizeof(s->temp.buf)
896 - s->temp.size - tmp);
897 s->rc.in_limit = s->temp.size + tmp;
898 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) {
899 s->temp.size += tmp;
903 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED;
906 s->rc.in = s->temp.buf;
907 s->rc.in_pos = 0;
909 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp)
912 s->lzma2.compressed -= s->rc.in_pos;
914 if (s->rc.in_pos < s->temp.size) {
915 s->temp.size -= s->rc.in_pos;
916 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos,
917 s->temp.size);
921 b->in_pos += s->rc.in_pos - s->temp.size;
922 s->temp.size = 0;
927 s->rc.in = b->in;
928 s->rc.in_pos = b->in_pos;
930 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED)
931 s->rc.in_limit = b->in_pos + s->lzma2.compressed;
933 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED;
935 if (!lzma_main(s))
938 in_avail = s->rc.in_pos - b->in_pos;
939 if (in_avail > s->lzma2.compressed)
942 s->lzma2.compressed -= in_avail;
943 b->in_pos = s->rc.in_pos;
948 if (in_avail > s->lzma2.compressed)
949 in_avail = s->lzma2.compressed;
951 memcpy(s->temp.buf, b->in + b->in_pos, in_avail);
952 s->temp.size = in_avail;
963 enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, struct xz_buf *b)
967 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) {
968 switch (s->lzma2.sequence) {
979 * Highest three bits (s->control & 0xE0):
991 * (s->control & 1F) are the highest bits of the
1007 s->lzma2.need_props = true;
1008 s->lzma2.need_dict_reset = false;
1009 dict_reset(&s->dict, b);
1010 } else if (s->lzma2.need_dict_reset) {
1015 s->lzma2.uncompressed = (tmp & 0x1F) << 16;
1016 s->lzma2.sequence = SEQ_UNCOMPRESSED_1;
1024 s->lzma2.need_props = false;
1025 s->lzma2.next_sequence
1028 } else if (s->lzma2.need_props) {
1032 s->lzma2.next_sequence
1035 lzma_reset(s);
1041 s->lzma2.sequence = SEQ_COMPRESSED_0;
1042 s->lzma2.next_sequence = SEQ_COPY;
1048 s->lzma2.uncompressed
1050 s->lzma2.sequence = SEQ_UNCOMPRESSED_2;
1054 s->lzma2.uncompressed
1056 s->lzma2.sequence = SEQ_COMPRESSED_0;
1060 s->lzma2.compressed
1062 s->lzma2.sequence = SEQ_COMPRESSED_1;
1066 s->lzma2.compressed
1068 s->lzma2.sequence = s->lzma2.next_sequence;
1072 if (!lzma_props(s, b->in[b->in_pos++]))
1075 s->lzma2.sequence = SEQ_LZMA_PREPARE;
1080 if (s->lzma2.compressed < RC_INIT_BYTES)
1083 if (!rc_read_init(&s->rc, b))
1086 s->lzma2.compressed -= RC_INIT_BYTES;
1087 s->lzma2.sequence = SEQ_LZMA_RUN;
1099 * multiple times without changing s->lzma2.sequence.
1101 dict_limit(&s->dict, min_t(size_t,
1103 s->lzma2.uncompressed));
1104 if (!lzma2_lzma(s, b))
1107 s->lzma2.uncompressed -= dict_flush(&s->dict, b);
1109 if (s->lzma2.uncompressed == 0) {
1110 if (s->lzma2.compressed > 0 || s->lzma.len > 0
1111 || !rc_is_finished(&s->rc))
1114 rc_reset(&s->rc);
1115 s->lzma2.sequence = SEQ_CONTROL;
1119 && s->temp.size
1120 < s->lzma2.compressed)) {
1127 dict_uncompressed(&s->dict, b, &s->lzma2.compressed);
1128 if (s->lzma2.compressed > 0)
1131 s->lzma2.sequence = SEQ_CONTROL;
1141 struct xz_dec_lzma2 *s = kmalloc(sizeof(*s), GFP_KERNEL);
1142 if (s == NULL)
1145 s->dict.mode = mode;
1146 s->dict.size_max = dict_max;
1149 s->dict.buf = vmalloc(dict_max);
1150 if (s->dict.buf == NULL) {
1151 kfree(s);
1155 s->dict.buf = NULL;
1156 s->dict.allocated = 0;
1159 return s;
1162 enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props)
1168 s->dict.size = 2 + (props & 1);
1169 s->dict.size <<= (props >> 1) + 11;
1171 if (DEC_IS_MULTI(s->dict.mode)) {
1172 if (s->dict.size > s->dict.size_max)
1175 s->dict.end = s->dict.size;
1177 if (DEC_IS_DYNALLOC(s->dict.mode)) {
1178 if (s->dict.allocated < s->dict.size) {
1179 s->dict.allocated = s->dict.size;
1180 vfree(s->dict.buf);
1181 s->dict.buf = vmalloc(s->dict.size);
1182 if (s->dict.buf == NULL) {
1183 s->dict.allocated = 0;
1190 s->lzma2.sequence = SEQ_CONTROL;
1191 s->lzma2.need_dict_reset = true;
1193 s->temp.size = 0;
1198 void xz_dec_lzma2_end(struct xz_dec_lzma2 *s)
1200 if (DEC_IS_MULTI(s->dict.mode))
1201 vfree(s->dict.buf);
1203 kfree(s);
1209 struct xz_dec_lzma2 s;
1215 struct xz_dec_lzma2 *s = &s_ptr->s;
1222 if (s->lzma2.sequence != SEQ_LZMA_RUN) {
1223 if (s->lzma2.sequence == SEQ_PROPERTIES) {
1232 if (!lzma_props(s, ~b->in[b->in_pos]))
1235 s->lzma2.sequence = SEQ_LZMA_PREPARE;
1245 if (s->lzma2.compressed < RC_INIT_BYTES
1246 || s->lzma2.compressed > (3U << 30))
1249 if (!rc_read_init(&s->rc, b))
1252 s->lzma2.compressed -= RC_INIT_BYTES;
1253 s->lzma2.sequence = SEQ_LZMA_RUN;
1255 dict_reset(&s->dict, b);
1259 if (DEC_IS_SINGLE(s->dict.mode))
1260 s->dict.end = b->out_size - b->out_pos;
1263 dict_limit(&s->dict, min_t(size_t, b->out_size - b->out_pos,
1264 s->lzma2.uncompressed));
1266 if (!lzma2_lzma(s, b))
1269 s->lzma2.uncompressed -= dict_flush(&s->dict, b);
1271 if (s->lzma2.uncompressed == 0) {
1272 if (s->lzma2.pedantic_microlzma) {
1273 if (s->lzma2.compressed > 0 || s->lzma.len > 0
1274 || !rc_is_finished(&s->rc))
1285 && s->temp.size < s->lzma2.compressed)
1293 struct xz_dec_microlzma *s;
1299 s = kmalloc(sizeof(*s), GFP_KERNEL);
1300 if (s == NULL)
1303 s->s.dict.mode = mode;
1304 s->s.dict.size = dict_size;
1307 s->s.dict.end = dict_size;
1309 s->s.dict.buf = vmalloc(dict_size);
1310 if (s->s.dict.buf == NULL) {
1311 kfree(s);
1316 return s;
1319 void xz_dec_microlzma_reset(struct xz_dec_microlzma *s, uint32_t comp_size,
1326 s->s.lzma2.compressed = comp_size;
1327 s->s.lzma2.uncompressed = uncomp_size;
1328 s->s.lzma2.pedantic_microlzma = uncomp_size_is_exact;
1330 s->s.lzma2.sequence = SEQ_PROPERTIES;
1331 s->s.temp.size = 0;
1334 void xz_dec_microlzma_end(struct xz_dec_microlzma *s)
1336 if (DEC_IS_MULTI(s->s.dict.mode))
1337 vfree(s->s.dict.buf);
1339 kfree(s);