[continued from previous message]

}

}

- #else
+#else // BLOCK_SORT_USE_HEAP_SORT

/* ---------- Heap Sort ---------- */

{
- UInt32 j;
+ size_t j;
for (j = 0; j < groupSize; j++)
{
- UInt32 sp = ind2[j] + NumSortedBytes; if (sp >= BlockSize) sp -= BlockSize;
- ind2[j] = sp;
+ size_t sp = ind2[j] + NumSortedBytes;
+ if (sp >= BlockSize)
+ sp -= BlockSize;
+ ind2[j] = (UInt32)sp;
}

HeapSortRef(ind2, Groups, groupSize);

/* Write Flags */
{
- UInt32 sp = ind2[0];
+ size_t sp = ind2[0];
UInt32 group = Groups[sp];

- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS
UInt32 *Flags = Groups + BlockSize;
- #else
- UInt32 prevGroupStart = 0;
- #endif
+#else
+ size_t prevGroupStart = 0;
+#endif

for (j = 1; j < groupSize; j++)
{
@@ -290,149 +341,210 @@
if (Groups[sp] != group)
{
group = Groups[sp];
- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS
{
- UInt32 t = groupOffset + j - 1;
+ const size_t t = groupOffset + j - 1;
Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
}
- #else
+#else
SetGroupSize(ind2 + prevGroupStart, j - prevGroupStart);
prevGroupStart = j;
- #endif
+#endif
}
}

- #ifndef BLOCK_SORT_EXTERNAL_FLAGS
+#ifndef BLOCK_SORT_EXTERNAL_FLAGS
SetGroupSize(ind2 + prevGroupStart, j - prevGroupStart);
- #endif
+#endif
}
{
/* Write new Groups values and Check that there are groups */
- UInt32 thereAreGroups = 0;
+ unsigned thereAreGroups = 0;
for (j = 0; j < groupSize; j++)
{
- UInt32 group = groupOffset + j;
- #ifndef BLOCK_SORT_EXTERNAL_FLAGS
+ size_t group = groupOffset + j;
+#ifndef BLOCK_SORT_EXTERNAL_FLAGS
UInt32 subGroupSize = ((ind2[j] & ~0xC0000000) >> kNumBitsMax);
- if ((ind2[j] & 0x40000000) != 0)
+ if (ind2[j] & 0x40000000)
subGroupSize += ((ind2[(size_t)j + 1] >> kNumBitsMax) << kNumExtra0Bits);
subGroupSize++;
for (;;)
{
- UInt32 original = ind2[j];
- UInt32 sp = original & kIndexMask;
- if (sp < NumSortedBytes) sp += BlockSize; sp -= NumSortedBytes;
- ind2[j] = sp | (original & ~kIndexMask);
- Groups[sp] = group;
+ const UInt32 original = ind2[j];
+ size_t sp = original & kIndexMask;
+ if (sp < NumSortedBytes)
+ sp += BlockSize;
+ sp -= NumSortedBytes;
+ ind2[j] = (UInt32)sp | (original & ~kIndexMask);
+ Groups[sp] = (UInt32)group;
if (--subGroupSize == 0)
break;
j++;
thereAreGroups = 1;
}
- #else
+#else
UInt32 *Flags = Groups + BlockSize;
for (;;)
{
- UInt32 sp = ind2[j]; if (sp < NumSortedBytes) sp += BlockSize; sp -= NumSortedBytes;
- ind2[j] = sp;
- Groups[sp] = group;
+ size_t sp = ind2[j];
+ if (sp < NumSortedBytes)
+ sp += BlockSize;
+ sp -= NumSortedBytes;
+ ind2[j] = (UInt32)sp;
+ Groups[sp] = (UInt32)group;
if ((Flags[(groupOffset + j) >> kNumFlagsBits] & (1 << ((groupOffset + j) & kFlagsMask))) == 0)
break;
j++;
thereAreGroups = 1;
}
- #endif
+#endif
}
return thereAreGroups;
}
}
- #endif
+#endif // BLOCK_SORT_USE_HEAP_SORT
}

+
/* conditions: blockSize > 0 */
-UInt32 BlockSort(UInt32 *Indices, const Byte *data, UInt32 blockSize)
+UInt32 BlockSort(UInt32 *Indices, const Byte *data, size_t blockSize)
{
UInt32 *counters = Indices + blockSize;
- UInt32 i;
+ size_t i;
UInt32 *Groups;
- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS
UInt32 *Flags;
- #endif
+#endif

- /* Radix-Sort for 2 bytes */
+/* Radix-Sort for 2 bytes */
+// { UInt32 yyy; for (yyy = 0; yyy < 100; yyy++) {
for (i = 0; i < kNumHashValues; i++)
counters[i] = 0;
- for (i = 0; i < blockSize - 1; i++)
- counters[((UInt32)data[i] << 8) | data[(size_t)i + 1]]++;
- counters[((UInt32)data[i] << 8) | data[0]]++;
+ {
+ const Byte *data2 = data;
+ size_t a = data[(size_t)blockSize - 1];
+ const Byte *data_lim = data + blockSize;
+ if (blockSize >= 4)
+ {
+ data_lim -= 3;
+ do
+ {
+ size_t b;
+ b = data2[0]; counters[(a << 8) | b]++;
+ a = data2[1]; counters[(b << 8) | a]++;
+ b = data2[2]; counters[(a << 8) | b]++;
+ a = data2[3]; counters[(b << 8) | a]++;
+ data2 += 4;
+ }
+ while (data2 < data_lim);
+ data_lim += 3;
+ }
+ while (data2 != data_lim)
+ {
+ size_t b = *data2++;
+ counters[(a << 8) | b]++;
+ a = b;
+ }
+ }
+// }}

Groups = counters + BS_TEMP_SIZE;
- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS
Flags = Groups + blockSize;
- {
- UInt32 numWords = (blockSize + kFlagsMask) >> kNumFlagsBits;
- for (i = 0; i < numWords; i++)
- Flags[i] = kAllFlags;
- }
- #endif
+ {
+ const size_t numWords = (blockSize + kFlagsMask) >> kNumFlagsBits;
+ for (i = 0; i < numWords; i++)
+ Flags[i] = kAllFlags;
+ }
+#endif

{
UInt32 sum = 0;
for (i = 0; i < kNumHashValues; i++)
{
- UInt32 groupSize = counters[i];
- if (groupSize > 0)
+ const UInt32 groupSize = counters[i];
+ counters[i] = sum;
+ sum += groupSize;
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS
+ if (groupSize)
{
- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
- UInt32 t = sum + groupSize - 1;
- Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask));
- #endif
- sum += groupSize;
+ const UInt32 t = sum - 1;
+ Flags[t >> kNumFlagsBits] &= ~((UInt32)1 << (t & kFlagsMask));
}
- counters[i] = sum - groupSize;
+#endif
}
+ }

- for (i = 0; i < blockSize - 1; i++)
- Groups[i] = counters[((UInt32)data[i] << 8) | data[(size_t)i + 1]];
- Groups[i] = counters[((UInt32)data[i] << 8) | data[0]];
+ for (i = 0; i < blockSize - 1; i++)
+ Groups[i] = counters[((unsigned)data[i] << 8) | data[(size_t)i + 1]];
+ Groups[i] = counters[((unsigned)data[i] << 8) | data[0]];
+
+ {
+#define SET_Indices(a, b, i) \
+ { UInt32 c; \
+ a = (a << 8) | (b); \
+ c = counters[a]; \
+ Indices[c] = (UInt32)i++; \
+ counters[a] = c + 1; \
+ }

- for (i = 0; i < blockSize - 1; i++)
- Indices[counters[((UInt32)data[i] << 8) | data[(size_t)i + 1]]++] = i;
- Indices[counters[((UInt32)data[i] << 8) | data[0]]++] = i;
-
- #ifndef BLOCK_SORT_EXTERNAL_FLAGS
+ size_t a = data[0];
+ const Byte *data_ptr = data + 1;
+ i = 0;
+ if (blockSize >= 3)
+ {
+ blockSize -= 2;
+ do
+ {
+ size_t b;
+ b = data_ptr[0]; SET_Indices(a, b, i)
+ a = data_ptr[1]; SET_Indices(b, a, i)
+ data_ptr += 2;
+ }
+ while (i < blockSize);
+ blockSize += 2;
+ }
+ if (i < blockSize - 1)
{
+ SET_Indices(a, data[(size_t)i + 1], i)
+ a = (Byte)a;
+ }
+ SET_Indices(a, data[0], i)
+ }
+
+#ifndef BLOCK_SORT_EXTERNAL_FLAGS
+ {
UInt32 prev = 0;
for (i = 0; i < kNumHashValues; i++)
{
- UInt32 prevGroupSize = counters[i] - prev;
+ const UInt32 prevGroupSize = counters[i] - prev;
if (prevGroupSize == 0)
continue;
SetGroupSize(Indices + prev, prevGroupSize);
prev = counters[i];
}
- }
- #endif
}
+#endif

{
- int NumRefBits;
- UInt32 NumSortedBytes;
- for (NumRefBits = 0; ((blockSize - 1) >> NumRefBits) != 0; NumRefBits++);
+ unsigned NumRefBits;
+ size_t NumSortedBytes;
+ for (NumRefBits = 0; ((blockSize - 1) >> NumRefBits) != 0; NumRefBits++)
+ {}
NumRefBits = 32 - NumRefBits;
if (NumRefBits > kNumRefBitsMax)
- NumRefBits = kNumRefBitsMax;
+ NumRefBits = kNumRefBitsMax;

for (NumSortedBytes = kNumHashBytes; ; NumSortedBytes <<= 1)
{
- #ifndef BLOCK_SORT_EXTERNAL_FLAGS
- UInt32 finishedGroupSize = 0;
- #endif
- UInt32 newLimit = 0;
+#ifndef BLOCK_SORT_EXTERNAL_FLAGS
+ size_t finishedGroupSize = 0;
+#endif
+ size_t newLimit = 0;
for (i = 0; i < blockSize;)
{
- UInt32 groupSize;
- #ifdef BLOCK_SORT_EXTERNAL_FLAGS
+ size_t groupSize;
+#ifdef BLOCK_SORT_EXTERNAL_FLAGS

if ((Flags[i >> kNumFlagsBits] & (1 << (i & kFlagsMask))) == 0)
{
@@ -441,56 +553,56 @@
}
for (groupSize = 1;
(Flags[(i + groupSize) >> kNumFlagsBits] & (1 << ((i + groupSize) & kFlagsMask))) != 0;
- groupSize++);
-
+ groupSize++)
+ {}
groupSize++;

- #else
+#else

- groupSize = ((Indices[i] & ~0xC0000000) >> kNumBitsMax);
+ groupSize = (Indices[i] & ~0xC0000000) >> kNumBitsMax;
{
- BoolInt finishedGroup = ((Indices[i] & 0x80000000) == 0);
- if ((Indices[i] & 0x40000000) != 0)
- {
- groupSize += ((Indices[(size_t)i + 1] >> kNumBitsMax) << kNumExtra0Bits);
- Indices[(size_t)i + 1] &= kIndexMask;
- }
- Indices[i] &= kIndexMask;
- groupSize++;
- if (finishedGroup || groupSize == 1)
- {
- Indices[i - finishedGroupSize] &= kIndexMask;
- if (finishedGroupSize > 1)
- Indices[(size_t)(i - finishedGroupSize) + 1] &= kIndexMask;
+ const BoolInt finishedGroup = ((Indices[i] & 0x80000000) == 0);
+ if (Indices[i] & 0x40000000)
{
- UInt32 newGroupSize = groupSize + finishedGroupSize;
- SetFinishedGroupSize(Indices + i - finishedGroupSize, newGroupSize)
- finishedGroupSize = newGroupSize;
+ groupSize += ((Indices[(size_t)i + 1] >> kNumBitsMax) << kNumExtra0Bits);
+ Indices[(size_t)i + 1] &= kIndexMask;
}
- i += groupSize;
- continue;
- }
- finishedGroupSize = 0;
+ Indices[i] &= kIndexMask;
+ groupSize++;
+ if (finishedGroup || groupSize == 1)
+ {
+ Indices[i - finishedGroupSize] &= kIndexMask;
+ if (finishedGroupSize > 1)
+ Indices[(size_t)(i - finishedGroupSize) + 1] &= kIndexMask;
+ {
+ const size_t newGroupSize = groupSize + finishedGroupSize;
+ SetFinishedGroupSize(Indices + i - finishedGroupSize, newGroupSize)
+ finishedGroupSize = newGroupSize;
+ }
+ i += groupSize;
+ continue;
+ }
+ finishedGroupSize = 0;
}

- #endif
+#endif

if (NumSortedBytes >= blockSize)
{
- UInt32 j;
+ size_t j;
for (j = 0; j < groupSize; j++)
{
- UInt32 t = (i + j);
+ size_t t = i + j;
/* Flags[t >> kNumFlagsBits] &= ~(1 << (t & kFlagsMask)); */
- Groups[Indices[t]] = t;
+ Groups[Indices[t]] = (UInt32)t;
}
}
else
if (SortGroup(blockSize, NumSortedBytes, i, groupSize, NumRefBits, Indices
- #ifndef BLOCK_SORT_USE_HEAP_SORT
- , 0, blockSize
- #endif
- ) != 0)
+ #ifndef BLOCK_SORT_USE_HEAP_SORT
+ , 0, blockSize
+ #endif
+ ))
newLimit = i + groupSize;
i += groupSize;
}
@@ -498,19 +610,19 @@
break;
}
}
- #ifndef BLOCK_SORT_EXTERNAL_FLAGS
+#ifndef BLOCK_SORT_EXTERNAL_FLAGS
for (i = 0; i < blockSize;)
{
- UInt32 groupSize = ((Indices[i] & ~0xC0000000) >> kNumBitsMax);
- if ((Indices[i] & 0x40000000) != 0)
+ size_t groupSize = (Indices[i] & ~0xC0000000) >> kNumBitsMax;
+ if (Indices[i] & 0x40000000)
{
- groupSize += ((Indices[(size_t)i + 1] >> kNumBitsMax) << kNumExtra0Bits);
+ groupSize += (Indices[(size_t)i + 1] >> kNumBitsMax) << kNumExtra0Bits;
Indices[(size_t)i + 1] &= kIndexMask;
}
Indices[i] &= kIndexMask;
groupSize++;
i += groupSize;
}
- #endif
+#endif
return Groups[0];
}
diff -Nru 7zip-24.09+dfsg/C/BwtSort.h 7zip-25.00+dfsg/C/BwtSort.h
--- 7zip-24.09+dfsg/C/BwtSort.h 2023-03-03 11:00:00.000000000 +0100
+++ 7zip-25.00+dfsg/C/BwtSort.h 2024-12-18 19:00:00.000000000 +0100
@@ -1,5 +1,5 @@
/* BwtSort.h -- BWT block sorting
-2023-03-03 : Igor Pavlov : Public domain */
+: Igor Pavlov : Public domain */

#ifndef ZIP7_INC_BWT_SORT_H
#define ZIP7_INC_BWT_SORT_H
@@ -10,16 +10,17 @@

/* use BLOCK_SORT_EXTERNAL_FLAGS if blockSize can be > 1M */
/* #define BLOCK_SORT_EXTERNAL_FLAGS */
+// #define BLOCK_SORT_EXTERNAL_FLAGS

#ifdef BLOCK_SORT_EXTERNAL_FLAGS
-#define BLOCK_SORT_EXTERNAL_SIZE(blockSize) ((((blockSize) + 31) >> 5)) +#define BLOCK_SORT_EXTERNAL_SIZE(blockSize) (((blockSize) + 31) >> 5)
#else
#define BLOCK_SORT_EXTERNAL_SIZE(blockSize) 0
#endif

#define BLOCK_SORT_BUF_SIZE(blockSize) ((blockSize) * 2 + BLOCK_SORT_EXTERNAL_SIZE(blockSize) + (1 << 16))

-UInt32 BlockSort(UInt32 *indices, const Byte *data, UInt32 blockSize);
+UInt32 BlockSort(UInt32 *indices, const Byte *data, size_t blockSize);

EXTERN_C_END