#include #include #define ENCODE_BUFFER_SIZE 0x10000 #define INPUT_BUFFER_SIZE (ENCODE_BUFFER_SIZE * 2) #define MAX_OFFSET 256 #define MIN_REPEAT 3 #define MAX_REPEAT (255 + MIN_REPEAT) #define MAX_STACK 999 /* Indices to input ring buffer. */ static int i_history, i_begin, i_end, /* Ring buffer of output code offsets (measured in number of instructions). */ code_offset[ENCODE_BUFFER_SIZE], /* Ring buffer of runtime stack sizes. */ stack_size[ENCODE_BUFFER_SIZE], /* Output code size (number of instructions). */ code_size, /* Number of already-encoded bytes that are available for matching. */ history_size, /* Offset of matched substring that will be referenced to replace buffered bytes. */ matched_input_offset, tentative_input_offset, /* Offset of code that will generate the matched substring. */ matched_code_offset, tentative_code_offset, /* Number of bytes in longest match. */ matched_length, /* Number of bytes from start of matched string that overlaps with start of input string. */ overlap, /* Number of bytes from start of match to current cursor position. */ prefix_length, i, j; /* Define a single header dictionary entry. */ #define D(d) ,#d /* Header text: - Uppercase letters causes a dictionary entry to be expanded recursively. - Tilde (~) causes the next letter to be copied as is. - Everything else is copied as is. */ static char *header_data[] = { /*M*/ ",", /*N*/ "Pzoltraak" /*O*/ D( ZifWUU Qjmp_bufPj;XmMIMi=1MlMk[999]={1<<30}M*o=k; Xmain(XdMchar**a){switch(S(j)){default:Yi;I=14; VP_P__LI~NE__VPpPT(I=_+1)VPqP(i=3M--R(jM*o--)):VNPcaseP_:i%2?YiMp:(_-4) %9?T(m|=1<<(_-I)):_-I-17?(putchar(m^32)MY*o)?p:q(l=m%256+3Mm=m/512+3Mi) ?(*o-=l)>0?m=i=0Mp:q((o[2]=*o 32 ) i > 76 && i < 91 ? Expand(header_data[i - 77]) : (void)putchar(i - 126 ? i : *++s); } /* Count number of bits in a 8-bit value. */ static int BitCount(int a) { assert(a >= 0); assert(a < 256); return a ? a % 2 + BitCount(a / 2) : 0; } int main(int argc, char **argv) { for(Expand(header_data[2]);;) { /* Fill ring buffer with enough bytes for the encoding process to consume, without overwriting old history entries. */ while( i_end - i_begin < ENCODE_BUFFER_SIZE && (i = getchar()) - EOF ) input[i_end++ % INPUT_BUFFER_SIZE] = i; if( i_begin == i_end ) break; assert(i_history <= i_begin); assert(i_begin <= i_end); /* Expire old code entries that are too far away to be matched. */ while( i_history < i_begin && ((i = code_offset[i_history % ENCODE_BUFFER_SIZE]) < 0 || code_size - i > MAX_OFFSET) ) { i_history++; } /* Match input against already-encoded bytes. */ history_size = i_begin - i_history; assert(history_size >= 0); matched_length = -1; for(i = 0; i < history_size; i++) /* Do not match against regions that was covered by repeat code, since there is no address to branch to. */ if( (tentative_code_offset = code_offset[(tentative_input_offset = i_history + i) % ENCODE_BUFFER_SIZE]) >= 0 ) { for(j = 0; /* Verify that length can still be encoded. */ j < MAX_REPEAT && /* Verify that we are only matching against what's been read. */ i_begin + j < i_end && /* Verify that historical substring matches incoming string. */ input[(tentative_input_offset + j) % INPUT_BUFFER_SIZE] == input[(i_begin + j) % INPUT_BUFFER_SIZE] && /* Verify that referencing the previous string here will not overflow the runtime stack. */ ( (overlap = tentative_input_offset + j - i_begin) < 0 ? /* Matching some string before the current read position. Stack size is guaranteed to be defined. */ stack_size[(tentative_input_offset + j) % ENCODE_BUFFER_SIZE] : /* Matching some string at or after the current read position. Stack size depends on how many times we have repeated the prefix. */ (prefix_length = i_begin - tentative_input_offset, stack_size[(tentative_input_offset + overlap % prefix_length) % ENCODE_BUFFER_SIZE] + 2 * overlap / prefix_length) ) <= MAX_STACK - 2; j++) { } if( j > matched_length || (j == matched_length && BitCount(code_size - tentative_code_offset - 1) < BitCount(code_size - matched_code_offset - 1)) ) matched_input_offset = tentative_input_offset, matched_code_offset = tentative_code_offset, matched_length = j; } if( matched_length >= MIN_REPEAT ) { /* Use previously generated code to cover incoming bytes. */ assert(matched_length - MIN_REPEAT >= 0); assert(matched_length - MIN_REPEAT < 256); assert(code_size - matched_code_offset - 1 >= 0); assert(code_size - matched_code_offset - 1 < 256); j = (matched_length - MIN_REPEAT) | ((code_size - matched_code_offset - 1) << 9) | (1 << 17); /* Advance ring buffer past encoded region. Also record address for start of region so that it can be used for future matches, while removing addresses for all subsequent bytes. */ for(i = 0; i < matched_length; code_offset[i_begin++ % ENCODE_BUFFER_SIZE] = i++ > 0 ? -1 : code_size) { stack_size[i_begin % ENCODE_BUFFER_SIZE] = stack_size[(matched_input_offset + i) % ENCODE_BUFFER_SIZE] + 2; assert(stack_size[i_begin % ENCODE_BUFFER_SIZE] >= 3); assert(stack_size[i_begin % ENCODE_BUFFER_SIZE] % 2 == 1); } code_size += 2; } else { /* Did not find a sufficiently long entry in history, output a literal byte. */ code_offset[i = i_begin % ENCODE_BUFFER_SIZE] = code_size++; stack_size[i] = 1; j = (input[i_begin++ % INPUT_BUFFER_SIZE] & 0xff) ^ 0x120; } /* Output a set of lines. */ for(; j; j /= 2) puts(header_data[j & 1] + 1); } return 0; }