Lines Matching refs:s
604 static uint16_t *lzma_literal_probs(struct xz_dec_lzma2 *s) in lzma_literal_probs() argument
606 uint32_t prev_byte = dict_get(&s->dict, 0); in lzma_literal_probs()
607 uint32_t low = prev_byte >> (8 - s->lzma.lc); in lzma_literal_probs()
608 uint32_t high = (s->dict.pos & s->lzma.literal_pos_mask) << s->lzma.lc; in lzma_literal_probs()
609 return s->lzma.literal[low + high]; in lzma_literal_probs()
613 static void lzma_literal(struct xz_dec_lzma2 *s) in lzma_literal() argument
622 probs = lzma_literal_probs(s); in lzma_literal()
624 if (lzma_state_is_literal(s->lzma.state)) { in lzma_literal()
625 symbol = rc_bittree(&s->rc, probs, 0x100); in lzma_literal()
628 match_byte = dict_get(&s->dict, s->lzma.rep0) << 1; in lzma_literal()
636 if (rc_bit(&s->rc, &probs[i])) { in lzma_literal()
646 dict_put(&s->dict, (uint8_t)symbol); in lzma_literal()
647 lzma_state_literal(&s->lzma.state); in lzma_literal()
651 static void lzma_len(struct xz_dec_lzma2 *s, struct lzma_len_dec *l, in lzma_len() argument
657 if (!rc_bit(&s->rc, &l->choice)) { in lzma_len()
660 s->lzma.len = MATCH_LEN_MIN; in lzma_len()
662 if (!rc_bit(&s->rc, &l->choice2)) { in lzma_len()
665 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; in lzma_len()
669 s->lzma.len = MATCH_LEN_MIN + LEN_LOW_SYMBOLS in lzma_len()
674 s->lzma.len += rc_bittree(&s->rc, probs, limit) - limit; in lzma_len()
678 static void lzma_match(struct xz_dec_lzma2 *s, uint32_t pos_state) in lzma_match() argument
684 lzma_state_match(&s->lzma.state); in lzma_match()
686 s->lzma.rep3 = s->lzma.rep2; in lzma_match()
687 s->lzma.rep2 = s->lzma.rep1; in lzma_match()
688 s->lzma.rep1 = s->lzma.rep0; in lzma_match()
690 lzma_len(s, &s->lzma.match_len_dec, pos_state); in lzma_match()
692 probs = s->lzma.dist_slot[lzma_get_dist_state(s->lzma.len)]; in lzma_match()
693 dist_slot = rc_bittree(&s->rc, probs, DIST_SLOTS) - DIST_SLOTS; in lzma_match()
696 s->lzma.rep0 = dist_slot; in lzma_match()
699 s->lzma.rep0 = 2 + (dist_slot & 1); in lzma_match()
702 s->lzma.rep0 <<= limit; in lzma_match()
703 probs = s->lzma.dist_special + s->lzma.rep0 in lzma_match()
705 rc_bittree_reverse(&s->rc, probs, in lzma_match()
706 &s->lzma.rep0, limit); in lzma_match()
708 rc_direct(&s->rc, &s->lzma.rep0, limit - ALIGN_BITS); in lzma_match()
709 s->lzma.rep0 <<= ALIGN_BITS; in lzma_match()
710 rc_bittree_reverse(&s->rc, s->lzma.dist_align, in lzma_match()
711 &s->lzma.rep0, ALIGN_BITS); in lzma_match()
720 static void lzma_rep_match(struct xz_dec_lzma2 *s, uint32_t pos_state) in lzma_rep_match() argument
724 if (!rc_bit(&s->rc, &s->lzma.is_rep0[s->lzma.state])) { in lzma_rep_match()
725 if (!rc_bit(&s->rc, &s->lzma.is_rep0_long[ in lzma_rep_match()
726 s->lzma.state][pos_state])) { in lzma_rep_match()
727 lzma_state_short_rep(&s->lzma.state); in lzma_rep_match()
728 s->lzma.len = 1; in lzma_rep_match()
732 if (!rc_bit(&s->rc, &s->lzma.is_rep1[s->lzma.state])) { in lzma_rep_match()
733 tmp = s->lzma.rep1; in lzma_rep_match()
735 if (!rc_bit(&s->rc, &s->lzma.is_rep2[s->lzma.state])) { in lzma_rep_match()
736 tmp = s->lzma.rep2; in lzma_rep_match()
738 tmp = s->lzma.rep3; in lzma_rep_match()
739 s->lzma.rep3 = s->lzma.rep2; in lzma_rep_match()
742 s->lzma.rep2 = s->lzma.rep1; in lzma_rep_match()
745 s->lzma.rep1 = s->lzma.rep0; in lzma_rep_match()
746 s->lzma.rep0 = tmp; in lzma_rep_match()
749 lzma_state_long_rep(&s->lzma.state); in lzma_rep_match()
750 lzma_len(s, &s->lzma.rep_len_dec, pos_state); in lzma_rep_match()
754 static bool lzma_main(struct xz_dec_lzma2 *s) in lzma_main() argument
762 if (dict_has_space(&s->dict) && s->lzma.len > 0) in lzma_main()
763 dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0); in lzma_main()
769 while (dict_has_space(&s->dict) && !rc_limit_exceeded(&s->rc)) { in lzma_main()
770 pos_state = s->dict.pos & s->lzma.pos_mask; in lzma_main()
772 if (!rc_bit(&s->rc, &s->lzma.is_match[ in lzma_main()
773 s->lzma.state][pos_state])) { in lzma_main()
774 lzma_literal(s); in lzma_main()
776 if (rc_bit(&s->rc, &s->lzma.is_rep[s->lzma.state])) in lzma_main()
777 lzma_rep_match(s, pos_state); in lzma_main()
779 lzma_match(s, pos_state); in lzma_main()
781 if (!dict_repeat(&s->dict, &s->lzma.len, s->lzma.rep0)) in lzma_main()
790 rc_normalize(&s->rc); in lzma_main()
799 static void lzma_reset(struct xz_dec_lzma2 *s) in lzma_reset() argument
804 s->lzma.state = STATE_LIT_LIT; in lzma_reset()
805 s->lzma.rep0 = 0; in lzma_reset()
806 s->lzma.rep1 = 0; in lzma_reset()
807 s->lzma.rep2 = 0; in lzma_reset()
808 s->lzma.rep3 = 0; in lzma_reset()
809 s->lzma.len = 0; in lzma_reset()
820 probs = s->lzma.is_match[0]; in lzma_reset()
824 rc_reset(&s->rc); in lzma_reset()
832 static bool lzma_props(struct xz_dec_lzma2 *s, uint8_t props) in lzma_props() argument
837 s->lzma.pos_mask = 0; in lzma_props()
840 ++s->lzma.pos_mask; in lzma_props()
843 s->lzma.pos_mask = (1 << s->lzma.pos_mask) - 1; in lzma_props()
845 s->lzma.literal_pos_mask = 0; in lzma_props()
848 ++s->lzma.literal_pos_mask; in lzma_props()
851 s->lzma.lc = props; in lzma_props()
853 if (s->lzma.lc + s->lzma.literal_pos_mask > 4) in lzma_props()
856 s->lzma.literal_pos_mask = (1 << s->lzma.literal_pos_mask) - 1; in lzma_props()
858 lzma_reset(s); in lzma_props()
879 static bool lzma2_lzma(struct xz_dec_lzma2 *s, struct xz_buf *b) in lzma2_lzma() argument
885 if (s->temp.size > 0 || s->lzma2.compressed == 0) { in lzma2_lzma()
886 tmp = 2 * LZMA_IN_REQUIRED - s->temp.size; in lzma2_lzma()
887 if (tmp > s->lzma2.compressed - s->temp.size) in lzma2_lzma()
888 tmp = s->lzma2.compressed - s->temp.size; in lzma2_lzma()
892 memcpy(s->temp.buf + s->temp.size, b->in + b->in_pos, tmp); in lzma2_lzma()
894 if (s->temp.size + tmp == s->lzma2.compressed) { in lzma2_lzma()
895 memzero(s->temp.buf + s->temp.size + tmp, in lzma2_lzma()
896 sizeof(s->temp.buf) in lzma2_lzma()
897 - s->temp.size - tmp); in lzma2_lzma()
898 s->rc.in_limit = s->temp.size + tmp; in lzma2_lzma()
899 } else if (s->temp.size + tmp < LZMA_IN_REQUIRED) { in lzma2_lzma()
900 s->temp.size += tmp; in lzma2_lzma()
904 s->rc.in_limit = s->temp.size + tmp - LZMA_IN_REQUIRED; in lzma2_lzma()
907 s->rc.in = s->temp.buf; in lzma2_lzma()
908 s->rc.in_pos = 0; in lzma2_lzma()
910 if (!lzma_main(s) || s->rc.in_pos > s->temp.size + tmp) in lzma2_lzma()
913 s->lzma2.compressed -= s->rc.in_pos; in lzma2_lzma()
915 if (s->rc.in_pos < s->temp.size) { in lzma2_lzma()
916 s->temp.size -= s->rc.in_pos; in lzma2_lzma()
917 memmove(s->temp.buf, s->temp.buf + s->rc.in_pos, in lzma2_lzma()
918 s->temp.size); in lzma2_lzma()
922 b->in_pos += s->rc.in_pos - s->temp.size; in lzma2_lzma()
923 s->temp.size = 0; in lzma2_lzma()
928 s->rc.in = b->in; in lzma2_lzma()
929 s->rc.in_pos = b->in_pos; in lzma2_lzma()
931 if (in_avail >= s->lzma2.compressed + LZMA_IN_REQUIRED) in lzma2_lzma()
932 s->rc.in_limit = b->in_pos + s->lzma2.compressed; in lzma2_lzma()
934 s->rc.in_limit = b->in_size - LZMA_IN_REQUIRED; in lzma2_lzma()
936 if (!lzma_main(s)) in lzma2_lzma()
939 in_avail = s->rc.in_pos - b->in_pos; in lzma2_lzma()
940 if (in_avail > s->lzma2.compressed) in lzma2_lzma()
943 s->lzma2.compressed -= in_avail; in lzma2_lzma()
944 b->in_pos = s->rc.in_pos; in lzma2_lzma()
949 if (in_avail > s->lzma2.compressed) in lzma2_lzma()
950 in_avail = s->lzma2.compressed; in lzma2_lzma()
952 memcpy(s->temp.buf, b->in + b->in_pos, in_avail); in lzma2_lzma()
953 s->temp.size = in_avail; in lzma2_lzma()
964 XZ_EXTERN enum xz_ret xz_dec_lzma2_run(struct xz_dec_lzma2 *s, in xz_dec_lzma2_run() argument
969 while (b->in_pos < b->in_size || s->lzma2.sequence == SEQ_LZMA_RUN) { in xz_dec_lzma2_run()
970 switch (s->lzma2.sequence) { in xz_dec_lzma2_run()
1009 s->lzma2.need_props = true; in xz_dec_lzma2_run()
1010 s->lzma2.need_dict_reset = false; in xz_dec_lzma2_run()
1011 dict_reset(&s->dict, b); in xz_dec_lzma2_run()
1012 } else if (s->lzma2.need_dict_reset) { in xz_dec_lzma2_run()
1017 s->lzma2.uncompressed = (tmp & 0x1F) << 16; in xz_dec_lzma2_run()
1018 s->lzma2.sequence = SEQ_UNCOMPRESSED_1; in xz_dec_lzma2_run()
1026 s->lzma2.need_props = false; in xz_dec_lzma2_run()
1027 s->lzma2.next_sequence in xz_dec_lzma2_run()
1030 } else if (s->lzma2.need_props) { in xz_dec_lzma2_run()
1034 s->lzma2.next_sequence in xz_dec_lzma2_run()
1037 lzma_reset(s); in xz_dec_lzma2_run()
1043 s->lzma2.sequence = SEQ_COMPRESSED_0; in xz_dec_lzma2_run()
1044 s->lzma2.next_sequence = SEQ_COPY; in xz_dec_lzma2_run()
1050 s->lzma2.uncompressed in xz_dec_lzma2_run()
1052 s->lzma2.sequence = SEQ_UNCOMPRESSED_2; in xz_dec_lzma2_run()
1056 s->lzma2.uncompressed in xz_dec_lzma2_run()
1058 s->lzma2.sequence = SEQ_COMPRESSED_0; in xz_dec_lzma2_run()
1062 s->lzma2.compressed in xz_dec_lzma2_run()
1064 s->lzma2.sequence = SEQ_COMPRESSED_1; in xz_dec_lzma2_run()
1068 s->lzma2.compressed in xz_dec_lzma2_run()
1070 s->lzma2.sequence = s->lzma2.next_sequence; in xz_dec_lzma2_run()
1074 if (!lzma_props(s, b->in[b->in_pos++])) in xz_dec_lzma2_run()
1077 s->lzma2.sequence = SEQ_LZMA_PREPARE; in xz_dec_lzma2_run()
1082 if (s->lzma2.compressed < RC_INIT_BYTES) in xz_dec_lzma2_run()
1085 if (!rc_read_init(&s->rc, b)) in xz_dec_lzma2_run()
1088 s->lzma2.compressed -= RC_INIT_BYTES; in xz_dec_lzma2_run()
1089 s->lzma2.sequence = SEQ_LZMA_RUN; in xz_dec_lzma2_run()
1103 dict_limit(&s->dict, min_t(size_t, in xz_dec_lzma2_run()
1105 s->lzma2.uncompressed)); in xz_dec_lzma2_run()
1106 if (!lzma2_lzma(s, b)) in xz_dec_lzma2_run()
1109 s->lzma2.uncompressed -= dict_flush(&s->dict, b); in xz_dec_lzma2_run()
1111 if (s->lzma2.uncompressed == 0) { in xz_dec_lzma2_run()
1112 if (s->lzma2.compressed > 0 || s->lzma.len > 0 in xz_dec_lzma2_run()
1113 || !rc_is_finished(&s->rc)) in xz_dec_lzma2_run()
1116 rc_reset(&s->rc); in xz_dec_lzma2_run()
1117 s->lzma2.sequence = SEQ_CONTROL; in xz_dec_lzma2_run()
1121 && s->temp.size in xz_dec_lzma2_run()
1122 < s->lzma2.compressed)) { in xz_dec_lzma2_run()
1129 dict_uncompressed(&s->dict, b, &s->lzma2.compressed); in xz_dec_lzma2_run()
1130 if (s->lzma2.compressed > 0) in xz_dec_lzma2_run()
1133 s->lzma2.sequence = SEQ_CONTROL; in xz_dec_lzma2_run()
1144 struct xz_dec_lzma2 *s = kmalloc(sizeof(*s), GFP_KERNEL); in xz_dec_lzma2_create() local
1145 if (s == NULL) in xz_dec_lzma2_create()
1148 s->dict.mode = mode; in xz_dec_lzma2_create()
1149 s->dict.size_max = dict_max; in xz_dec_lzma2_create()
1152 s->dict.buf = vmalloc(dict_max); in xz_dec_lzma2_create()
1153 if (s->dict.buf == NULL) { in xz_dec_lzma2_create()
1154 kfree(s); in xz_dec_lzma2_create()
1158 s->dict.buf = NULL; in xz_dec_lzma2_create()
1159 s->dict.allocated = 0; in xz_dec_lzma2_create()
1162 return s; in xz_dec_lzma2_create()
1165 XZ_EXTERN enum xz_ret xz_dec_lzma2_reset(struct xz_dec_lzma2 *s, uint8_t props) in xz_dec_lzma2_reset() argument
1171 s->dict.size = 2 + (props & 1); in xz_dec_lzma2_reset()
1172 s->dict.size <<= (props >> 1) + 11; in xz_dec_lzma2_reset()
1174 if (DEC_IS_MULTI(s->dict.mode)) { in xz_dec_lzma2_reset()
1175 if (s->dict.size > s->dict.size_max) in xz_dec_lzma2_reset()
1178 s->dict.end = s->dict.size; in xz_dec_lzma2_reset()
1180 if (DEC_IS_DYNALLOC(s->dict.mode)) { in xz_dec_lzma2_reset()
1181 if (s->dict.allocated < s->dict.size) { in xz_dec_lzma2_reset()
1182 s->dict.allocated = s->dict.size; in xz_dec_lzma2_reset()
1183 vfree(s->dict.buf); in xz_dec_lzma2_reset()
1184 s->dict.buf = vmalloc(s->dict.size); in xz_dec_lzma2_reset()
1185 if (s->dict.buf == NULL) { in xz_dec_lzma2_reset()
1186 s->dict.allocated = 0; in xz_dec_lzma2_reset()
1193 s->lzma2.sequence = SEQ_CONTROL; in xz_dec_lzma2_reset()
1194 s->lzma2.need_dict_reset = true; in xz_dec_lzma2_reset()
1196 s->temp.size = 0; in xz_dec_lzma2_reset()
1201 XZ_EXTERN void xz_dec_lzma2_end(struct xz_dec_lzma2 *s) in xz_dec_lzma2_end() argument
1203 if (DEC_IS_MULTI(s->dict.mode)) in xz_dec_lzma2_end()
1204 vfree(s->dict.buf); in xz_dec_lzma2_end()
1206 kfree(s); in xz_dec_lzma2_end()
1212 struct xz_dec_lzma2 s; member
1218 struct xz_dec_lzma2 *s = &s_ptr->s; in xz_dec_microlzma_run() local
1225 if (s->lzma2.sequence != SEQ_LZMA_RUN) { in xz_dec_microlzma_run()
1226 if (s->lzma2.sequence == SEQ_PROPERTIES) { in xz_dec_microlzma_run()
1235 if (!lzma_props(s, ~b->in[b->in_pos])) in xz_dec_microlzma_run()
1238 s->lzma2.sequence = SEQ_LZMA_PREPARE; in xz_dec_microlzma_run()
1248 if (s->lzma2.compressed < RC_INIT_BYTES in xz_dec_microlzma_run()
1249 || s->lzma2.compressed > (3U << 30)) in xz_dec_microlzma_run()
1252 if (!rc_read_init(&s->rc, b)) in xz_dec_microlzma_run()
1255 s->lzma2.compressed -= RC_INIT_BYTES; in xz_dec_microlzma_run()
1256 s->lzma2.sequence = SEQ_LZMA_RUN; in xz_dec_microlzma_run()
1258 dict_reset(&s->dict, b); in xz_dec_microlzma_run()
1262 if (DEC_IS_SINGLE(s->dict.mode)) in xz_dec_microlzma_run()
1263 s->dict.end = b->out_size - b->out_pos; in xz_dec_microlzma_run()
1266 dict_limit(&s->dict, min_t(size_t, b->out_size - b->out_pos, in xz_dec_microlzma_run()
1267 s->lzma2.uncompressed)); in xz_dec_microlzma_run()
1269 if (!lzma2_lzma(s, b)) in xz_dec_microlzma_run()
1272 s->lzma2.uncompressed -= dict_flush(&s->dict, b); in xz_dec_microlzma_run()
1274 if (s->lzma2.uncompressed == 0) { in xz_dec_microlzma_run()
1275 if (s->lzma2.pedantic_microlzma) { in xz_dec_microlzma_run()
1276 if (s->lzma2.compressed > 0 || s->lzma.len > 0 in xz_dec_microlzma_run()
1277 || !rc_is_finished(&s->rc)) in xz_dec_microlzma_run()
1288 && s->temp.size < s->lzma2.compressed) in xz_dec_microlzma_run()
1296 struct xz_dec_microlzma *s; in xz_dec_microlzma_alloc() local
1302 s = kmalloc(sizeof(*s), GFP_KERNEL); in xz_dec_microlzma_alloc()
1303 if (s == NULL) in xz_dec_microlzma_alloc()
1306 s->s.dict.mode = mode; in xz_dec_microlzma_alloc()
1307 s->s.dict.size = dict_size; in xz_dec_microlzma_alloc()
1310 s->s.dict.end = dict_size; in xz_dec_microlzma_alloc()
1312 s->s.dict.buf = vmalloc(dict_size); in xz_dec_microlzma_alloc()
1313 if (s->s.dict.buf == NULL) { in xz_dec_microlzma_alloc()
1314 kfree(s); in xz_dec_microlzma_alloc()
1319 return s; in xz_dec_microlzma_alloc()
1322 void xz_dec_microlzma_reset(struct xz_dec_microlzma *s, uint32_t comp_size, in xz_dec_microlzma_reset() argument
1329 s->s.lzma2.compressed = comp_size; in xz_dec_microlzma_reset()
1330 s->s.lzma2.uncompressed = uncomp_size; in xz_dec_microlzma_reset()
1331 s->s.lzma2.pedantic_microlzma = uncomp_size_is_exact; in xz_dec_microlzma_reset()
1333 s->s.lzma2.sequence = SEQ_PROPERTIES; in xz_dec_microlzma_reset()
1334 s->s.temp.size = 0; in xz_dec_microlzma_reset()
1337 void xz_dec_microlzma_end(struct xz_dec_microlzma *s) in xz_dec_microlzma_end() argument
1339 if (DEC_IS_MULTI(s->s.dict.mode)) in xz_dec_microlzma_end()
1340 vfree(s->s.dict.buf); in xz_dec_microlzma_end()
1342 kfree(s); in xz_dec_microlzma_end()