| changeset 42937 | 69de49c4e39c |
| parent 42070 | 675775c33ab6 |
| child 43994 | de7838053207 |
| 42936:2da754532dd3 | 42937:69de49c4e39c |
|---|---|
81 const BYTE* match; |
81 const BYTE* match; |
82 U32* smallerPtr = bt + 2*(current&btMask); |
82 U32* smallerPtr = bt + 2*(current&btMask); |
83 U32* largerPtr = smallerPtr + 1; |
83 U32* largerPtr = smallerPtr + 1; |
84 U32 matchIndex = *smallerPtr; /* this candidate is unsorted : next sorted candidate is reached through *smallerPtr, while *largerPtr contains previous unsorted candidate (which is already saved and can be overwritten) */ |
84 U32 matchIndex = *smallerPtr; /* this candidate is unsorted : next sorted candidate is reached through *smallerPtr, while *largerPtr contains previous unsorted candidate (which is already saved and can be overwritten) */ |
85 U32 dummy32; /* to be nullified at the end */ |
85 U32 dummy32; /* to be nullified at the end */ |
86 U32 const windowLow = ms->window.lowLimit; |
86 U32 const windowValid = ms->window.lowLimit; |
87 U32 const maxDistance = 1U << cParams->windowLog; |
|
88 U32 const windowLow = (current - windowValid > maxDistance) ? current - maxDistance : windowValid; |
|
89 |
|
87 |
90 |
88 DEBUGLOG(8, "ZSTD_insertDUBT1(%u) (dictLimit=%u, lowLimit=%u)", |
91 DEBUGLOG(8, "ZSTD_insertDUBT1(%u) (dictLimit=%u, lowLimit=%u)", |
89 current, dictLimit, windowLow); |
92 current, dictLimit, windowLow); |
90 assert(current >= btLow); |
93 assert(current >= btLow); |
91 assert(ip < iend); /* condition for ZSTD_count */ |
94 assert(ip < iend); /* condition for ZSTD_count */ |
237 size_t const h = ZSTD_hashPtr(ip, hashLog, mls); |
240 size_t const h = ZSTD_hashPtr(ip, hashLog, mls); |
238 U32 matchIndex = hashTable[h]; |
241 U32 matchIndex = hashTable[h]; |
239 |
242 |
240 const BYTE* const base = ms->window.base; |
243 const BYTE* const base = ms->window.base; |
241 U32 const current = (U32)(ip-base); |
244 U32 const current = (U32)(ip-base); |
242 U32 const windowLow = ms->window.lowLimit; |
245 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, current, cParams->windowLog); |
243 |
246 |
244 U32* const bt = ms->chainTable; |
247 U32* const bt = ms->chainTable; |
245 U32 const btLog = cParams->chainLog - 1; |
248 U32 const btLog = cParams->chainLog - 1; |
246 U32 const btMask = (1 << btLog) - 1; |
249 U32 const btMask = (1 << btLog) - 1; |
247 U32 const btLow = (btMask >= current) ? 0 : current - btMask; |
250 U32 const btLow = (btMask >= current) ? 0 : current - btMask; |
488 const BYTE* const base = ms->window.base; |
491 const BYTE* const base = ms->window.base; |
489 const BYTE* const dictBase = ms->window.dictBase; |
492 const BYTE* const dictBase = ms->window.dictBase; |
490 const U32 dictLimit = ms->window.dictLimit; |
493 const U32 dictLimit = ms->window.dictLimit; |
491 const BYTE* const prefixStart = base + dictLimit; |
494 const BYTE* const prefixStart = base + dictLimit; |
492 const BYTE* const dictEnd = dictBase + dictLimit; |
495 const BYTE* const dictEnd = dictBase + dictLimit; |
493 const U32 lowLimit = ms->window.lowLimit; |
|
494 const U32 current = (U32)(ip-base); |
496 const U32 current = (U32)(ip-base); |
497 const U32 maxDistance = 1U << cParams->windowLog; |
|
498 const U32 lowestValid = ms->window.lowLimit; |
|
499 const U32 withinMaxDistance = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid; |
|
500 const U32 isDictionary = (ms->loadedDictEnd != 0); |
|
501 const U32 lowLimit = isDictionary ? lowestValid : withinMaxDistance; |
|
495 const U32 minChain = current > chainSize ? current - chainSize : 0; |
502 const U32 minChain = current > chainSize ? current - chainSize : 0; |
496 U32 nbAttempts = 1U << cParams->searchLog; |
503 U32 nbAttempts = 1U << cParams->searchLog; |
497 size_t ml=4-1; |
504 size_t ml=4-1; |
498 |
505 |
499 /* HC4 match finder */ |
506 /* HC4 match finder */ |
610 |
617 |
611 |
618 |
612 /* ******************************* |
619 /* ******************************* |
613 * Common parser - lazy strategy |
620 * Common parser - lazy strategy |
614 *********************************/ |
621 *********************************/ |
615 FORCE_INLINE_TEMPLATE |
622 typedef enum { search_hashChain, search_binaryTree } searchMethod_e; |
616 size_t ZSTD_compressBlock_lazy_generic( |
623 |
624 FORCE_INLINE_TEMPLATE size_t |
|
625 ZSTD_compressBlock_lazy_generic( |
|
617 ZSTD_matchState_t* ms, seqStore_t* seqStore, |
626 ZSTD_matchState_t* ms, seqStore_t* seqStore, |
618 U32 rep[ZSTD_REP_NUM], |
627 U32 rep[ZSTD_REP_NUM], |
619 const void* src, size_t srcSize, |
628 const void* src, size_t srcSize, |
620 const U32 searchMethod, const U32 depth, |
629 const searchMethod_e searchMethod, const U32 depth, |
621 ZSTD_dictMode_e const dictMode) |
630 ZSTD_dictMode_e const dictMode) |
622 { |
631 { |
623 const BYTE* const istart = (const BYTE*)src; |
632 const BYTE* const istart = (const BYTE*)src; |
624 const BYTE* ip = istart; |
633 const BYTE* ip = istart; |
625 const BYTE* anchor = istart; |
634 const BYTE* anchor = istart; |
631 |
640 |
632 typedef size_t (*searchMax_f)( |
641 typedef size_t (*searchMax_f)( |
633 ZSTD_matchState_t* ms, |
642 ZSTD_matchState_t* ms, |
634 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); |
643 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); |
635 searchMax_f const searchMax = dictMode == ZSTD_dictMatchState ? |
644 searchMax_f const searchMax = dictMode == ZSTD_dictMatchState ? |
636 (searchMethod ? ZSTD_BtFindBestMatch_dictMatchState_selectMLS : ZSTD_HcFindBestMatch_dictMatchState_selectMLS) : |
645 (searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_dictMatchState_selectMLS |
637 (searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS); |
646 : ZSTD_HcFindBestMatch_dictMatchState_selectMLS) : |
647 (searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_selectMLS |
|
648 : ZSTD_HcFindBestMatch_selectMLS); |
|
638 U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0; |
649 U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0; |
639 |
650 |
640 const ZSTD_matchState_t* const dms = ms->dictMatchState; |
651 const ZSTD_matchState_t* const dms = ms->dictMatchState; |
641 const U32 dictLowestIndex = dictMode == ZSTD_dictMatchState ? |
652 const U32 dictLowestIndex = dictMode == ZSTD_dictMatchState ? |
642 dms->window.dictLimit : 0; |
653 dms->window.dictLimit : 0; |
651 0; |
662 0; |
652 const U32 dictAndPrefixLength = (U32)(ip - prefixLowest + dictEnd - dictLowest); |
663 const U32 dictAndPrefixLength = (U32)(ip - prefixLowest + dictEnd - dictLowest); |
653 |
664 |
654 /* init */ |
665 /* init */ |
655 ip += (dictAndPrefixLength == 0); |
666 ip += (dictAndPrefixLength == 0); |
656 ms->nextToUpdate3 = ms->nextToUpdate; |
|
657 if (dictMode == ZSTD_noDict) { |
667 if (dictMode == ZSTD_noDict) { |
658 U32 const maxRep = (U32)(ip - prefixLowest); |
668 U32 const maxRep = (U32)(ip - prefixLowest); |
659 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0; |
669 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0; |
660 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0; |
670 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0; |
661 } |
671 } |
842 /* Save reps for next block */ |
852 /* Save reps for next block */ |
843 rep[0] = offset_1 ? offset_1 : savedOffset; |
853 rep[0] = offset_1 ? offset_1 : savedOffset; |
844 rep[1] = offset_2 ? offset_2 : savedOffset; |
854 rep[1] = offset_2 ? offset_2 : savedOffset; |
845 |
855 |
846 /* Return the last literals size */ |
856 /* Return the last literals size */ |
847 return iend - anchor; |
857 return (size_t)(iend - anchor); |
848 } |
858 } |
849 |
859 |
850 |
860 |
851 size_t ZSTD_compressBlock_btlazy2( |
861 size_t ZSTD_compressBlock_btlazy2( |
852 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
862 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
853 void const* src, size_t srcSize) |
863 void const* src, size_t srcSize) |
854 { |
864 { |
855 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_noDict); |
865 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD_noDict); |
856 } |
866 } |
857 |
867 |
858 size_t ZSTD_compressBlock_lazy2( |
868 size_t ZSTD_compressBlock_lazy2( |
859 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
869 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
860 void const* src, size_t srcSize) |
870 void const* src, size_t srcSize) |
861 { |
871 { |
862 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_noDict); |
872 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_noDict); |
863 } |
873 } |
864 |
874 |
865 size_t ZSTD_compressBlock_lazy( |
875 size_t ZSTD_compressBlock_lazy( |
866 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
876 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
867 void const* src, size_t srcSize) |
877 void const* src, size_t srcSize) |
868 { |
878 { |
869 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_noDict); |
879 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_noDict); |
870 } |
880 } |
871 |
881 |
872 size_t ZSTD_compressBlock_greedy( |
882 size_t ZSTD_compressBlock_greedy( |
873 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
883 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
874 void const* src, size_t srcSize) |
884 void const* src, size_t srcSize) |
875 { |
885 { |
876 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_noDict); |
886 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_noDict); |
877 } |
887 } |
878 |
888 |
879 size_t ZSTD_compressBlock_btlazy2_dictMatchState( |
889 size_t ZSTD_compressBlock_btlazy2_dictMatchState( |
880 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
890 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
881 void const* src, size_t srcSize) |
891 void const* src, size_t srcSize) |
882 { |
892 { |
883 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_dictMatchState); |
893 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD_dictMatchState); |
884 } |
894 } |
885 |
895 |
886 size_t ZSTD_compressBlock_lazy2_dictMatchState( |
896 size_t ZSTD_compressBlock_lazy2_dictMatchState( |
887 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
897 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
888 void const* src, size_t srcSize) |
898 void const* src, size_t srcSize) |
889 { |
899 { |
890 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_dictMatchState); |
900 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_dictMatchState); |
891 } |
901 } |
892 |
902 |
893 size_t ZSTD_compressBlock_lazy_dictMatchState( |
903 size_t ZSTD_compressBlock_lazy_dictMatchState( |
894 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
904 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
895 void const* src, size_t srcSize) |
905 void const* src, size_t srcSize) |
896 { |
906 { |
897 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_dictMatchState); |
907 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_dictMatchState); |
898 } |
908 } |
899 |
909 |
900 size_t ZSTD_compressBlock_greedy_dictMatchState( |
910 size_t ZSTD_compressBlock_greedy_dictMatchState( |
901 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
911 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
902 void const* src, size_t srcSize) |
912 void const* src, size_t srcSize) |
903 { |
913 { |
904 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_dictMatchState); |
914 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_dictMatchState); |
905 } |
915 } |
906 |
916 |
907 |
917 |
908 FORCE_INLINE_TEMPLATE |
918 FORCE_INLINE_TEMPLATE |
909 size_t ZSTD_compressBlock_lazy_extDict_generic( |
919 size_t ZSTD_compressBlock_lazy_extDict_generic( |
910 ZSTD_matchState_t* ms, seqStore_t* seqStore, |
920 ZSTD_matchState_t* ms, seqStore_t* seqStore, |
911 U32 rep[ZSTD_REP_NUM], |
921 U32 rep[ZSTD_REP_NUM], |
912 const void* src, size_t srcSize, |
922 const void* src, size_t srcSize, |
913 const U32 searchMethod, const U32 depth) |
923 const searchMethod_e searchMethod, const U32 depth) |
914 { |
924 { |
915 const BYTE* const istart = (const BYTE*)src; |
925 const BYTE* const istart = (const BYTE*)src; |
916 const BYTE* ip = istart; |
926 const BYTE* ip = istart; |
917 const BYTE* anchor = istart; |
927 const BYTE* anchor = istart; |
918 const BYTE* const iend = istart + srcSize; |
928 const BYTE* const iend = istart + srcSize; |
926 const BYTE* const dictStart = dictBase + lowestIndex; |
936 const BYTE* const dictStart = dictBase + lowestIndex; |
927 |
937 |
928 typedef size_t (*searchMax_f)( |
938 typedef size_t (*searchMax_f)( |
929 ZSTD_matchState_t* ms, |
939 ZSTD_matchState_t* ms, |
930 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); |
940 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); |
931 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_extDict_selectMLS : ZSTD_HcFindBestMatch_extDict_selectMLS; |
941 searchMax_f searchMax = searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_extDict_selectMLS : ZSTD_HcFindBestMatch_extDict_selectMLS; |
932 |
942 |
933 U32 offset_1 = rep[0], offset_2 = rep[1]; |
943 U32 offset_1 = rep[0], offset_2 = rep[1]; |
934 |
944 |
935 /* init */ |
945 /* init */ |
936 ms->nextToUpdate3 = ms->nextToUpdate; |
|
937 ip += (ip == prefixStart); |
946 ip += (ip == prefixStart); |
938 |
947 |
939 /* Match Loop */ |
948 /* Match Loop */ |
940 while (ip < ilimit) { |
949 while (ip < ilimit) { |
941 size_t matchLength=0; |
950 size_t matchLength=0; |
1068 /* Save reps for next block */ |
1077 /* Save reps for next block */ |
1069 rep[0] = offset_1; |
1078 rep[0] = offset_1; |
1070 rep[1] = offset_2; |
1079 rep[1] = offset_2; |
1071 |
1080 |
1072 /* Return the last literals size */ |
1081 /* Return the last literals size */ |
1073 return iend - anchor; |
1082 return (size_t)(iend - anchor); |
1074 } |
1083 } |
1075 |
1084 |
1076 |
1085 |
1077 size_t ZSTD_compressBlock_greedy_extDict( |
1086 size_t ZSTD_compressBlock_greedy_extDict( |
1078 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1087 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1079 void const* src, size_t srcSize) |
1088 void const* src, size_t srcSize) |
1080 { |
1089 { |
1081 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 0); |
1090 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0); |
1082 } |
1091 } |
1083 |
1092 |
1084 size_t ZSTD_compressBlock_lazy_extDict( |
1093 size_t ZSTD_compressBlock_lazy_extDict( |
1085 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1094 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1086 void const* src, size_t srcSize) |
1095 void const* src, size_t srcSize) |
1087 |
1096 |
1088 { |
1097 { |
1089 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 1); |
1098 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1); |
1090 } |
1099 } |
1091 |
1100 |
1092 size_t ZSTD_compressBlock_lazy2_extDict( |
1101 size_t ZSTD_compressBlock_lazy2_extDict( |
1093 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1102 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1094 void const* src, size_t srcSize) |
1103 void const* src, size_t srcSize) |
1095 |
1104 |
1096 { |
1105 { |
1097 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 2); |
1106 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2); |
1098 } |
1107 } |
1099 |
1108 |
1100 size_t ZSTD_compressBlock_btlazy2_extDict( |
1109 size_t ZSTD_compressBlock_btlazy2_extDict( |
1101 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1110 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], |
1102 void const* src, size_t srcSize) |
1111 void const* src, size_t srcSize) |
1103 |
1112 |
1104 { |
1113 { |
1105 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 1, 2); |
1114 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2); |
1106 } |
1115 } |