Mercurial > public > mercurial-scm > hg

comparison contrib/python-zstandard/zstd/compress/zstd_lazy.c @ 42937:69de49c4e39c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
zstandard: vendor python-zstandard 0.12 The upstream source distribution from PyPI was extracted. Unwanted files were removed. The clang-format ignore list was updated to reflect the new source of files. test-repo-compengines.t was updated to reflect a change in behavior of the zstd library. The project contains a vendored copy of zstandard 1.4.3. The old version was 1.3.8. This should result in some minor performance wins. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D6858
author Gregory Szorc <gregory.szorc@gmail.com>
date Sun, 15 Sep 2019 20:04:00 -0700
parents 675775c33ab6
children de7838053207
comparison
equal deleted inserted replaced
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 }