windows-nt/Source/XPSP1/NT/ds/xpress/xencode.i
2020-09-26 16:20:57 +08:00

656 lines
21 KiB
OpenEdge ABL

/* ------------------------------------------------------------------------ */
/* */
/* Copyright (c) Microsoft Corporation, 2000-2001. All rights reserved. */
/* Copyright (c) Andrew Kadatch, 1991-2001. All rights reserved. */
/* */
/* Microsoft Confidential -- do not redistribute. */
/* */
/* ------------------------------------------------------------------------ */
#if CHAIN >= 2
INLINE void find_match (prs *p)
{
const uchar *p1;
xint k, n, m;
#if CHAIN >= 3
xint chain = v.chain;
#endif
p->x.z_next[0] = (z_index_t) (k = n = v.orig.pos);
do
{
m = p->x.z_next[k];
#ifdef i386
{
uint16 c = *(__unaligned uint16 *)((p1 = v.orig.ptr + v.match.len - 1) + n);
#if CHAIN >= 3
do
{
if (--chain < 0)
return;
#endif /* CHAIN >= 3 */
k = p->x.z_next[m]; if (*(__unaligned uint16 *) (p1 + m) == c) goto same_m;
m = p->x.z_next[k]; if (*(__unaligned uint16 *) (p1 + k) == c) goto same_k;
k = p->x.z_next[m]; if (*(__unaligned uint16 *) (p1 + m) == c) goto same_m;
m = p->x.z_next[k]; if (*(__unaligned uint16 *) (p1 + k) == c) goto same_k;
k = p->x.z_next[m]; if (*(__unaligned uint16 *) (p1 + m) == c) goto same_m;
m = p->x.z_next[k]; if (*(__unaligned uint16 *) (p1 + k) == c) goto same_k;
k = p->x.z_next[m]; if (*(__unaligned uint16 *) (p1 + m) == c) goto same_m;
m = p->x.z_next[k]; if (*(__unaligned uint16 *) (p1 + k) == c) goto same_k;
#if CHAIN < 3
if (*(__unaligned uint16 *) (p1 + m) == c) goto same_m;
return;
#else
}
while (1);
#endif /* CHAIN < 3 */
#else /* !i386 */
{
const uchar *p0 = v.orig.ptr + v.match.len;
const uchar c0 = p0[n];
const uchar c1 = (p1 = p0 - 1)[n];
#if CHAIN >= 3
do
{
if (--chain < 0)
return;
#endif /* CHAIN >= 3 */
k = p->x.z_next[m]; if (p0[m] == c0 && p1[m] == c1) goto same_m;
m = p->x.z_next[k]; if (p0[k] == c0 && p1[k] == c1) goto same_k;
k = p->x.z_next[m]; if (p0[m] == c0 && p1[m] == c1) goto same_m;
m = p->x.z_next[k]; if (p0[k] == c0 && p1[k] == c1) goto same_k;
k = p->x.z_next[m]; if (p0[m] == c0 && p1[m] == c1) goto same_m;
m = p->x.z_next[k]; if (p0[k] == c0 && p1[k] == c1) goto same_k;
k = p->x.z_next[m]; if (p0[m] == c0 && p1[m] == c1) goto same_m;
m = p->x.z_next[k]; if (p0[k] == c0 && p1[k] == c1) goto same_k;
#if CHAIN < 3
if (p0[m] == c0 && p1[m] == c1) goto same_m;
return;
#else
}
while (1);
#endif /* CHAIN < 3 */
#endif /* i386 */
same_m:
k = m;
same_k:
if (k == n)
return;
#if MAX_OFFSET < BUFF_SIZE_LOG
if (n - k >= (1 << MAX_OFFSET))
return;
#endif
}
{
const uchar *p2;
p1 = v.orig.ptr;
p2 = p1 + k;
p1 += n;
#ifdef i386
if ((m = *(__unaligned uint32 *)p2 ^ *(__unaligned uint32 *)p1) != 0)
{
#if MIN_MATCH <= 3
if ((m & 0xffffff) == 0 && v.match.len <= 2 && p1 + 3 <= v.orig.end)
{
v.match.len = 3;
v.match.pos = k;
}
#endif /* MIN_MATCH <= 3 */
goto cont;
}
#else /* !i386 */
if (p1[0] != p2[0] || p1[1] != p2[1] || p1[2] != p2[2])
goto cont;
if (p1[3] != p2[3])
{
#if MIN_MATCH <= 3
if (v.match.len <= 2 && p1 + 3 <= v.orig.end)
{
v.match.len = 3;
v.match.pos = k;
}
#endif /* MIN_MATCH <= 3 */
goto cont;
}
#endif /* i386 */
if (p1 <= v.orig.end_16)
{
goto entry4;
do
{
#define X(i) if (p1[i] != p2[i]) {p1 += i; goto chk;}
X(0); X(1); X(2); X(3);
entry4:
X(4); X(5); X(6); X(7); X(8);
X(9); X(10); X(11); X(12); X(13); X(14); X(15);
#undef X
p1 += 16; p2 += 16;
}
while (p1 <= v.orig.end_16);
}
while (p1 != v.orig.end)
{
if (*p1 != *p2)
goto chk;
++p1;
++p2;
}
#define SET_LENGTH() \
n = -n; \
n += (xint) (p1 - v.orig.ptr); \
if (n > v.match.len) \
{ \
v.match.len = n; \
v.match.pos = k; \
}
SET_LENGTH ();
return;
}
chk:
SET_LENGTH ();
cont:
n = v.orig.pos;
}
while (CHAIN >= 3);
}
static void encode_pass1 (prs *p)
{
uchar *ptr = v.temp.ptr;
do
{
if (p->x.z_next[v.orig.pos] == 0)
goto literal;
v.match.len = MIN_MATCH-1;
find_match (p);
if (v.match.len <= MIN_MATCH-1)
{
literal:
write_lit (p, ptr, v.orig.ptr[v.orig.pos]);
v.orig.pos += 1;
}
else
{
ptr = write_ptr (p, ptr, v.orig.pos - v.match.pos, v.match.len);
v.orig.pos += v.match.len;
}
}
while (v.orig.pos < v.orig.stop);
v.temp.ptr = ptr;
}
#endif /* CHAIN >= 2 */
#if CHAIN < 2
#if CODING != CODING_DIRECT2 || !defined (i386)
static void encode_pass1 (prs *p)
{
const uchar *b, *b1, *stop;
uchar *ptr;
#if CHAIN > 0
xint pos = v.orig.pos;
#endif
b = v.orig.ptr;
v.orig.ptr_stop = stop = b + v.orig.stop;
b += v.orig.pos;
ptr = v.temp.ptr;
if (b != v.orig.ptr)
goto literal_entry;
for (;;)
{
do
{
#if MAX_OFFSET < BUFF_SIZE_LOG
next:
#endif
write_lit (p, ptr, *b);
++b;
#if CHAIN > 0
++pos;
#endif
literal_entry:
if (b >= stop)
goto ret;
{
uxint h;
#if CHAIN <= 0
h = Q_HASH_SUM (b);
b1 = p->x.q_last[h];
p->x.q_last[h] = b;
#else
assert (pos == (xint) (b - v.orig.ptr));
h = Z_HASH_SUM (b);
b1 = v.orig.ptr + p->x.z_next[h];
p->x.z_next[h] = (z_index_t) pos;
#endif
}
#if MAX_OFFSET < BUFF_SIZE_LOG
if (b1 <= b - (1 << MAX_OFFSET))
goto next;
#endif
}
while (b1 == 0 || b1[0] != b[0] || b1[1] != b[1] || b1[2] != b[2]);
assert ((xint) (v.orig.ptr + v.orig.size - b) > 7);
{
const uchar *b0 = b;
if (b <= v.orig.end_16)
goto match_entry_3;
goto match_careful;
do
{
#define X(i) if (b1[i] != b[i]) {b += i; b1 += i; goto eval_len;}
X(0); X(1); X(2);
match_entry_3:
X(3); X(4); X(5); X(6); X(7);
X(8); X(9); X(10); X(11);
X(12); X(13); X(14); X(15);
#undef X
b += 16; b1 += 16;
}
while (b <= v.orig.end_16);
match_careful:
while (b != v.orig.end && *b1 == *b)
{
++b;
++b1;
}
eval_len:
#if BUFF_SIZE_LOG > 16
#error
#endif
ptr = write_ptr (p, ptr, (xint) (b - b1), (xint) (b - b0));
b1 = b0;
}
++b1;
#if CHAIN > 0
++pos;
#endif
if (b > v.orig.end_3)
{
while (b1 < v.orig.end_3)
{
#if CHAIN <= 0
p->x.q_last[Q_HASH_SUM (b1)] = b1;
#else
assert (pos == (xint) (b1 - v.orig.ptr));
p->x.z_next[Z_HASH_SUM (b1)] = (z_index_t) pos;
++pos;
#endif
++b1;
}
goto literal_entry;
}
do
{
#if CHAIN <= 0
p->x.q_last[Q_HASH_SUM (b1)] = b1;
#else
assert (pos == (xint) (b1 - v.orig.ptr));
p->x.z_next[Z_HASH_SUM (b1)] = (z_index_t) pos;
++pos;
#endif
++b1;
}
while (b1 != b);
goto literal_entry;
}
ret:
v.orig.pos = (xint) (b - v.orig.ptr);
v.temp.ptr = ptr;
}
#else /* CODING != CODING_DIRECT2 */
static void encode_pass1 (prs *PrsPtr)
{
#define PRS edx
#define TAG ebp
#define TAGW bp
// access to prs structure fields
#define V [PRS - SIZE prs] prs.c
// TAG = tag_mask; adjusts TAG (tag_mask), V.temp.tag_ptr, and ebx (output pointer)
#define WRITE_TAG_MASK() \
__asm mov ecx, V.temp.tag_ptr \
__asm mov V.temp.tag_ptr, ebx \
__asm add ebx, 4 \
__asm mov [ecx], TAG \
__asm mov TAG, 1
#if CHAIN <= 0
// access to respective hash table entry
#define Q_HTABLE(idx) dword ptr [PRS + idx*4] prs.x.q_last
// evaluate hash sum of [esi] on eax; spoils eax, ecx, TAG
#define Q_HASH_SUM_ASM() \
__asm movzx eax, byte ptr [esi] \
__asm movzx ecx, byte ptr [esi+1] \
__asm movzx edi, byte ptr [esi+2] \
__asm lea ecx, [ecx + eax * (1 << (Q_HASH_SH1 - Q_HASH_SH2))] \
__asm lea eax, [edi + ecx * (1 << Q_HASH_SH2)]
#else
// access to respective hash table entry
#define Z_HTABLE(idx) word ptr [PRS + idx*2] prs.x.z_next
// evaluate hash sum of [esi] on eax; spoils eax, ecx, edi
#define Z_HASH_SUM_ASM() \
__asm movzx eax, byte ptr [esi] \
__asm movzx ecx, byte ptr [esi+1] \
__asm movzx edi, byte ptr [esi+2] \
__asm movzx eax, word ptr z_hash_map[eax*2] \
__asm movzx ecx, word ptr z_hash_map[ecx*2][512] \
__asm movzx edi, word ptr z_hash_map[edi*2][1024] \
__asm xor eax, ecx \
__asm xor eax, edi
#endif /* CHAIN <= 0 */
__asm
{
push ebp // save ebp
mov PRS, PrsPtr // PRS = PrsPtr (globally)
// esi = b
// edi = b1
// ebx = V.prs.temp.ptr
// TAG = V.temp.tag_mask
mov esi, V.orig.ptr // obtain b, b1, temp.ptr, and temp.mask
mov eax, V.orig.stop
add eax, esi
mov V.orig.ptr_stop, eax // and set orig.ptr_stop by orig.stop
add esi, V.orig.pos
mov ebx, V.temp.ptr
mov TAG, V.temp.tag_mask
cmp esi, V.orig.ptr // if beginning of buffer
jne write_literal_entry // then write literal immediately
write_literal:
mov al, [esi] // read the literal
inc ebx // shift dst ptr in advance
inc esi // shift src ptr to next character
mov [ebx-1], al // emit literal
add TAG, TAG // write tag bit 0
jc write_literal_tag_new // save tag word if it is full
write_literal_tag_done:
write_literal_entry:
cmp esi, V.orig.ptr_stop // processed everything?
jae pass1_stop // yes, stop
#if CHAIN <= 0
Q_HASH_SUM_ASM () // evaluate hash sum
#if MAX_OFFSET < BUFF_SIZE_LOG
lea ecx, [esi - (1 << MAX_OFFSET) + 1] // min. allowed left bound
#endif
mov edi, Q_HTABLE (eax) // edi = candidate ptr
mov Q_HTABLE (eax), esi // save current ptr
#else
Z_HASH_SUM_ASM () // evaluate hash sum
mov ecx,V.orig.ptr
movzx di, Z_HTABLE (eax) // edi = offset to candidate ptr
sub esi, ecx // esi = offset to current ptr
add edi, ecx // edi = candidate ptr
mov Z_HTABLE (eax), si // store current ptr offset
add esi, ecx // restore current ptr
#if MAX_OFFSET < BUFF_SIZE_LOG
lea ecx, [esi - (1 << MAX_OFFSET) + 1] // min. allowed left bound
#endif
#endif /* CHAIN <= 0 */
#if MAX_OFFSET < BUFF_SIZE_LOG
cmp edi, ecx // canidate is in window?
js write_literal // no, then emit literal
#endif
test edi, edi // is it NULL?
jz write_literal // emit literal if so
mov eax, [esi] // get first 4 src bytes
sub eax, [edi] // diff them with first 4 candidate bytes
je length_4 // if no diff then match is at least 4 bytes
test eax, 0xffffff // is there any difference in first 3 bytes?
jne write_literal // if yes emit literal
mov ecx, 3 // save match ptr of length ECX
sub edi, esi // edi = -offset
write_small_ptr:
lea eax, [esi+ecx] // eax = end of src match
not edi // edi = offset-1
add ebx, 2 // adjust output ptr in advance
shl edi, DIRECT2_LEN_LOG // make room for length
inc esi // esi = next substring (current already inserted)
lea edi, [edi + ecx - MIN_MATCH] // combine offset and shoft length
stc // set carry bit
mov [ebx-2], di // save packed pointer
adc TAG, TAG // write tag bit 1
jc write_pointer_tag_new // write tag word when it is full
write_pointer_tag_done:
cmp eax, V.orig.end_3 // is it too close to end of buffer?
ja insert_tail // if yes process is specially avoiding read overrun
#if CHAIN <= 0
push TAG // save tag_mask
mov TAG, eax // eax = end-of-match
insert_all:
Q_HASH_SUM_ASM () // evaluate hash sum
mov Q_HTABLE (eax), esi // save current ptr
inc esi // shift to next position
cmp esi, TAG // inserted all substrings in the match?
jne insert_all // continue until finished
pop TAG // restore tag_mask value
jmp write_literal_entry // process next substring
#else
push TAG // save tag_mask
push eax // save end-of-match
mov TAG, esi // TAG = current ptr
sub TAG, V.orig.ptr // TAG = current ptr offset
insert_all:
Z_HASH_SUM_ASM () // evaluate hash sum
mov Z_HTABLE (eax), TAGW // save current offset
inc esi // shift to next position
inc TAG // increase offset
cmp esi, [esp] // inserted all substrings in the match?
jne insert_all // continue until finished
pop eax // remove end-of-match ptr from the stack
pop TAG // restore tag_mask
jmp write_literal_entry // process next substring
#endif /* CHAIN <= 0 */
length_4:
#define KNOWN_LENGTH 4 // we know that first 4 bytes match
#if DIRECT2_MAX_LEN + MIN_MATCH >= 8
mov eax, [esi+4] // fetch next 4 bytes
sub eax, [edi+4] // get the diff between src and candidate
jz length_8 // do long compare if 8+ bytes match
bsf ecx, eax // ecx = # of first non-zero bit
sub edi, esi // edi = -offset
shr ecx, 3 // ecx = # of first non-zero byte
not edi // edi = offset-1
add ecx, 4 // plus previous 4 matching bytes = match length
add ebx, 2 // adjust output ptr in advance
lea eax, [esi+ecx] // eax = end of src match
shl edi, DIRECT2_LEN_LOG // make room for length
inc esi // esi = next substring (current already inserted)
lea edi,[edi+ecx-MIN_MATCH] // combine offset and shoft length
stc // set carry bit
mov [ebx-2], di // save packed pointer
adc TAG, TAG // write tag bit 1
jnc write_pointer_tag_done // write tag word when it is full
WRITE_TAG_MASK ()
jmp write_pointer_tag_done
length_8:
#undef KNOWN_LENGTH
#define KNOWN_LENGTH 8 // we know that first 8 bytes match
#endif /* DIRECT2_MAX_LEN + MIN_MATCH >= 8 */
mov eax, esi // eax = beginning of the string
mov ecx, V.orig.end // ecx = end of buffer
add esi, KNOWN_LENGTH // shift to first untested src byte
add edi, KNOWN_LENGTH // shift to first untested candidate
sub ecx, esi // ecx = max compare length
rep cmpsb // compare src and candidate
je match_complete // if eq then match till end of buffer
match_complete_done:
lea ecx, [esi-1] // ecx = end of match
sub edi, esi // edi = -offset
sub ecx, eax // ecx = match length
mov esi, eax // esi = src ptr
cmp ecx, DIRECT2_MAX_LEN+MIN_MATCH // small length?
jb write_small_ptr // write ptr if so
not edi // edi = offset-1
lea eax, [esi+ecx] // eax = end of match
shl edi, DIRECT2_LEN_LOG // make room for length
sub ecx, DIRECT2_MAX_LEN+MIN_MATCH // decrease the length
add edi, DIRECT2_MAX_LEN // mark length as long
push eax // save end of match
mov [ebx], di // write packed pointer
mov al, cl // al = (ecx <= 15 ? cl : 15)
cmp ecx, 15
jbe match_less_15
mov al, 15
match_less_15:
mov edi, V.stat.ptr // edi = quad_ptr
add ebx, 2 // wrote 2 bytes, move output ptr
test edi, edi // if quad_ptr != NULL write upper 4 bits
jne match_have_ptr
mov V.stat.ptr, ebx // make new tag_ptr
mov [ebx], al // write lower 4 bits
inc ebx // wrote 1 byte, move output ptr
jmp match_done_ptr // continue execution
match_have_ptr:
shl al, 4 // will write into upper 4 bits
mov dword ptr V.stat.ptr, 0 // no more space in this quad_bit[0]
or [edi], al // write upper 4 bits
match_done_ptr:
sub ecx, 15 // adjusted length < 15?
jae match_long_long_length // if not continue encoding
match_finish_2:
inc esi // shift to next output position
pop eax // restore eax = end-of-match
stc // set carry flag
adc TAG, TAG // write tag bit 1
jnc write_pointer_tag_done // continue execution if do not need to flush
write_pointer_tag_new: // write tag word and return to pointers
WRITE_TAG_MASK ()
jmp write_pointer_tag_done
match_long_long_length:
mov [ebx], cl // write the length as a byte
inc ebx // move output ptr
cmp ecx, 255 // adjusted length fits in byte?
jb match_finish_2 // if so ptr is written
add ecx, DIRECT2_MAX_LEN+15 // restore full length - MIN_MATCH
mov byte ptr [ebx-1], 255 // mark byte length as "to be continued"
mov [ebx], cx // write full length
add ebx, 2 // move output ptr
jmp match_finish_2
write_literal_tag_new: // write tag word and return to literals
WRITE_TAG_MASK ()
jmp write_literal_tag_done
match_complete: // cmpsb compared till end of buffer
inc esi // increase esi
inc edi // increase edi
jmp match_complete_done // resume execution
insert_tail:
push eax // save end-of-match
jmp insert_tail_1
insert_tail_next:
#if CHAIN <= 0
Q_HASH_SUM_ASM () // evaluate hash sum
mov Q_HTABLE (eax), esi // insert current src pointer
#else
Z_HASH_SUM_ASM () // evaluate hash sum
mov ecx, esi
sub ecx, V.orig.ptr // ecx = current ptr offset
mov Z_HTABLE (eax), cx // save offset in hash table
#endif /* CHAIN <= 0 */
inc esi // and move it to next substring
insert_tail_1: // end of match exceeds end_3 -- be careful
cmp esi, V.orig.end_3 // inserted up to end_3?
jb insert_tail_next // if not continue
pop esi // esi = end of match
jmp write_literal_entry
pass1_stop:
mov V.temp.ptr, ebx // save register variables
mov V.temp.tag_mask, TAG
sub esi, V.orig.ptr
mov V.orig.pos, esi
pop ebp // restore ebp
} /* __asm */
}
#undef V
#undef PRS
#undef TAG
#undef TAGW
#undef Q_HTABLE
#undef Q_HASH_SUM_ASM
#undef Z_HTABLE
#undef Z_HASH_SUM_ASM
#undef KNOWN_LENGTH
#endif /* CODING != CODING_DIRECT2 */
#endif /* CHAIN < 2 */
#undef CHAIN
#undef find_match
#undef encode_pass1