Add initial (incomplete, fugly) version of alf compressor, in C.

2 files changed, 296 insertions, 1 deletions

diff --git a/src/Makefile b/src/Makefile
index 57d389e..c19ac60 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -41,10 +41,11 @@ CFLAGS=-DVERSION='"$(VERSION)"' -Wall -I../f65 $(COPT)
 
 UNALF_OBJS=unalf.o io.o listalf.o extract.o f65.o glob.o opts.o usage.o self.o asmcode.o
 ALFSUM_OBJS=alfsum.o self.o
+ALF_OBJS=alf.o
 
 .PHONY: all clean install crosswin windows windows-upload realclean
 
-all: unalf unalf.1 alfsum alfsum.1
+all: unalf unalf.1 alfsum alfsum.1 alf
 
 # unalf and alfsum need explicit rules for BSD make compatibility.
 # without them, bmake tries to run "cc -o unalf unalf.c" which ain't
diff --git a/src/alf.c b/src/alf.c
new file mode 100644
index 0000000..4b5b871
--- /dev/null
+++ b/src/alf.c
@@ -0,0 +1,294 @@
+/* eventual options:
+	-a append
+	-o overwrite (instead of backup~)
+	-v verbose
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifndef u8
+#define u8 unsigned char
+#define u16 unsigned short
+#endif
+
+#define INITIAL_BITS 9
+#define MAX_BITS 12
+#define MAX_TOKENS (1 << MAX_BITS)
+#define TOK_RESET 256
+#define TOK_INCBITS 257
+#define INIT_TOKEN 258 /* 256 = reset dict, 257 = token_bits++ */
+
+#define MAX_INPUT_SIZE (1 << 24)
+
+u8 input_buf[MAX_INPUT_SIZE];
+u8 output_buf[MAX_INPUT_SIZE];
+u8 byte_tokens[256];
+int input_len, output_len, out_bitpos;
+
+typedef struct s_token {
+	u8 *start;
+	u16 length;
+} token_t;
+
+token_t tokentab[MAX_TOKENS];
+
+FILE *out_file, *in_file;
+const char *out_filename, *in_filename;
+int token_bits;
+int max_token;
+int curr_token;
+long hdr_compsize_pos;
+
+void init_table(void) {
+	int i;
+
+	memset(tokentab, 0, sizeof(tokentab));
+
+	token_bits = INITIAL_BITS;
+	max_token = 1 << INITIAL_BITS;
+	curr_token = INIT_TOKEN;
+
+	for(i = 0; i < 256; i++) {
+		byte_tokens[i] = (u8)i;
+		tokentab[i].start = &byte_tokens[i];
+		tokentab[i].length = 1;
+	}
+}
+
+#if 0
+void writequad(unsigned long data) {
+	int i;
+
+	for(i = 0; i < 4; i++) {
+		fputc(data & 0xff, out_file);
+		data >>= 8;
+	}
+}
+
+void write_cksum(void) {
+	int i;
+	u16 cksum = 0;
+
+	for(i = 0; i < input_len; i++)
+		cksum += input_buf[i];
+
+	fputc(cksum & 0xff, out_file);
+	fputc(cksum >> 8, out_file);
+}
+#endif
+
+void store_quad(int pos, unsigned long data) {
+	int i;
+
+	for(i = 0; i < 4; i++) {
+		output_buf[pos++] = data & 0xff;
+		data >>= 8;
+	}
+}
+
+void store_cksum(void) {
+	int i;
+	u16 cksum = 0;
+
+	for(i = 0; i < input_len; i++)
+		cksum += input_buf[i];
+
+	output_buf[23] = cksum & 0xff;
+	output_buf[24] = cksum >> 8;
+}
+
+void create_header(void) {
+	output_buf[0] = 0x1a;
+	output_buf[1] = 0x0f;
+	/* TODO: atari-ize filename */
+	strncat((char *)&output_buf[2], in_filename, 13);
+	output_buf[14] = 0x00;
+	store_quad(15, 0); /* compressed size, fill in later */
+	store_quad(19, 0); /* date/time (TODO: real timestamp) */
+	store_cksum();
+	store_quad(25, input_len);
+	output_len = 29;
+}
+
+#if 0
+void write_header(void) {
+	/* TODO: atari-ize the filename */
+	fwrite("\x1a\x0f", 1, 2, out_file);
+	fwrite(in_filename, 1, 12, out_file); /* TODO: capitalize, etc */
+	fwrite("\0", 1, 1, out_file);
+	if((hdr_compsize_pos = ftell(out_file)) < 0) {
+		perror("ftell");
+		exit(1);
+	}
+	writequad(0); /* compressed size, will fill in later */
+	writequad(0); /* TODO: real timestamps */
+	write_cksum();
+	writequad(input_len);
+	exit(0);
+}
+#endif
+
+/*
+void update_header(void) {
+	if(fseek(out_file, hdr_compsize_pos, SEEK_SET) < 0) {
+		perror("fseek");
+		exit(1);
+	}
+	writequad(output_len);
+	fseek(out_file, 0, SEEK_END);
+}
+*/
+
+void update_header(void) {
+	store_quad(15, output_len - 29);
+}
+
+void open_input(const char *filename) {
+	in_filename = filename;
+	if(!(in_file = fopen(in_filename, "rb"))) {
+		perror(in_filename);
+		exit(1);
+	}
+}
+
+/*
+void dump_table(void) {
+	int i, j;
+	printf("tokens: %d\n", curr_token);
+	for(i = INIT_TOKEN; i < curr_token; i++) {
+	}
+}
+*/
+
+void append_bit(int bit) {
+	output_buf[output_len] |= (bit << (7 - out_bitpos));
+	out_bitpos++;
+	if(out_bitpos == 8) {
+		out_bitpos = 0;
+		output_len++;
+	}
+}
+
+void store_token(int tok) {
+	int mask;
+
+	for(mask = 1 << (token_bits - 1); mask; mask >>= 1) {
+		append_bit(tok & mask ? 1 : 0);
+		// printf("%d", tok & mask ? 1 : 0);
+	}
+	// putchar('\n');
+
+	#if 0
+	if(tok == ' ')
+		printf("\" \"");
+	else if(tok > 255)
+		printf("tok(%d)", tok - 256);
+	else if(tok < ' ' || tok > 126)
+		printf("$%02x", tok);
+	else
+		printf("%c", tok);
+	putchar('\n');
+	#endif
+
+}
+
+int match_token(int pos) {
+	int i, bestmatch = -1;
+
+	for(i = 0; i < curr_token; i++) {
+		if(i == TOK_RESET || i == TOK_INCBITS)
+			continue;
+		if(memcmp(&input_buf[pos], tokentab[i].start, tokentab[i].length) == 0)
+			bestmatch = i;
+	}
+
+	if(bestmatch == -1) {
+		fprintf(stderr, "bestmatch is -1, this should never happen\n");
+		exit(1);
+	}
+
+	return bestmatch;
+}
+
+void make_token(int start, int end) {
+	tokentab[curr_token].start = &input_buf[start];
+	tokentab[curr_token].length = end - start + 1;
+	curr_token++;
+	if(curr_token == max_token) {
+		store_token(TOK_INCBITS);
+		if(token_bits == 12) {
+			store_token(TOK_RESET);
+			token_bits = 9;
+			init_table();
+		} else {
+			token_bits++;
+		}
+		max_token = 1 << token_bits;
+	}
+}
+
+void crunch(void) {
+	int in_pos = 0, new_pos;
+	int token;
+
+	out_bitpos = 0;
+
+	store_token(TOK_RESET);
+
+	while(in_pos < input_len) {
+		token = match_token(in_pos);
+		store_token(token);
+		new_pos = in_pos + tokentab[token].length;
+		// printf("   in_pos %d, new_pos %d\n", in_pos, new_pos);
+		if(new_pos < input_len)
+			make_token(in_pos, new_pos);
+		in_pos = new_pos;
+	}
+
+	store_token(TOK_INCBITS);
+	if(out_bitpos) output_len++;
+	update_header();
+}
+
+void crunch_file(const char *filename) {
+	init_table();
+
+	printf("Crunching %s\n", filename);
+	open_input(filename);
+
+	/* read in entire input, couldn't do it this way on the Atari */
+	input_len = fread(input_buf, 1, MAX_INPUT_SIZE - 1, in_file);
+	output_len = 0;
+	fclose(in_file);
+
+	create_header();
+
+	crunch();
+	fwrite(output_buf, 1, output_len, out_file);
+
+	// dump_table();
+}
+
+int main(int argc, char **argv) {
+	if(argc < 3) {
+		fprintf(stderr, "usage: alf archive.alf file [file ...]\n");
+		exit(1);
+	}
+
+	argv++;
+	out_file = fopen(*argv, "wb");
+	if(!out_file) {
+		perror(*argv);
+		exit(1);
+	}
+	argv++;
+
+	while(*argv)
+		crunch_file(*argv++);
+
+	fclose(out_file);
+
+	exit(0);
+}