Hutter Prize Enwik XML Parsing

XML.c

//Full guide : https://leetarxiv.substack.com/p/writing-a-wikipedia-mediawiki-parser
//This code assumes access to Enwik8 and "English.dic" file in https://github.com/kaitz/fxcm/tree/main
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <sys/mman.h>
#include <stdbool.h>
#include <math.h>
#include <ctype.h>
#define INDEX(x, y, cols) ((x) * (cols) + (y))

//clear && gcc main.c -lm -o m.o && ./m.o
typedef unsigned char  U8;
typedef unsigned short U16;
typedef unsigned int   U32;
typedef unsigned long long int U64;
inline int min(int a, int b) {return a<b?a:b;}
inline int max(int a, int b) {return a<b?b:a;}
#define ispowerof2(x) ((x&(x-1))==0)
/*Start dictionary*/
// wfgets reads until \n, then replaces \n with \0
// Input:  "hello\n"
// Output: "hello" (length = 5)
int wfgets(char *str, int count, FILE  *fp)
{
	int c, i = 0;
	while (i<count-1 && ((c=getc(fp))!=EOF))
	{
		str[i++]=c; if (c=='\n')str[i-1]=0;
		if(c=='\n')break;
	}
	str[i]=0;
	return i;
}
char *s;
char *dictW[44515];
U8 dictWLen[44515];
char *dictM[472];
int codeword2sym[256]; 
const int dict1size=80;
const int dict2size=32;
int dict12size=dict1size*dict2size;
int sizeDict,sizeDict2;
// decoded codewords for wordmodel
U32 cwTEXT;           // text
U32 cwNOWIKI;         // nowiki
U32 cwMATH;           // math
U32 cwPRE;            // pre
U32 cwPAGE;           // page image category user wikipedia
U32 cwIMAGE;
U32 cwCATEGORY;
U32 cwUSER;
U32 cwWIKIPEDIA;
//
U32 cwTABLE;
U32 cwTD;
//
U32 cwSEE;
U32 cwALSO;
//
U32 cwEXTERNAL;
U32 cwLINKS;
//
U32 cwREFERENCES;     // References
U32 cwBIBLIOGRAPHY;   // Bibliography

U32 cwIS;
U32 cwWITH;
U32 cwTHE;
U32 cwON,cwIN;
U32 cwWWW,cwHTTP;
U32 cwISBN;
void LoadDictionary(FILE  *file)
{
	int line_count=0,len=0;
	s=(char *)malloc(8192*8);
	while ((len=wfgets(s, 8192*8, file)) ) 
	{
		dictW[line_count]=(char *)malloc(len);
		memcpy(dictW[line_count],  s, len);
		dictWLen[line_count]=(len-1);
		//printf("%d,%s\n",len,dictW[line_count]);
		if (cwTEXT==0 && strcmp(dictW[line_count], "text")==0) cwTEXT=line_count;
		else if (cwNOWIKI==0 && strcmp(dictW[line_count], "nowiki")==0) cwNOWIKI=line_count;
		else if (cwMATH==0 && strcmp(dictW[line_count], "math")==0) cwMATH=line_count;
		else if (cwPRE==0 && strcmp(dictW[line_count], "pre")==0) cwPRE=line_count;
		else if (cwPAGE==0 && strcmp(dictW[line_count], "page")==0) cwPAGE=line_count;
		else if (cwIMAGE==0 && strcmp(dictW[line_count], "image")==0) cwIMAGE=line_count;
		else if (cwCATEGORY==0 && strcmp(dictW[line_count], "category")==0) cwCATEGORY=line_count;
		else if (cwUSER==0 && strcmp(dictW[line_count], "user")==0) cwUSER=line_count;
		else if (cwWIKIPEDIA==0 && strcmp(dictW[line_count], "wikipedia")==0) cwWIKIPEDIA=line_count;
		else if (cwTABLE==0 && strcmp(dictW[line_count], "table")==0) cwTABLE=line_count;
		else if (cwTD==0 && strcmp(dictW[line_count], "td")==0) cwTD=line_count;

		else if (cwEXTERNAL==0 && strcmp(dictW[line_count], "external")==0) cwEXTERNAL=line_count;
		else if (cwLINKS==0 && strcmp(dictW[line_count], "links")==0) cwLINKS=line_count;
		else if (cwSEE==0 && strcmp(dictW[line_count], "see")==0) cwSEE=line_count;
		else if (cwALSO==0 && strcmp(dictW[line_count], "also")==0) cwALSO=line_count;
		else if (cwREFERENCES==0 && strcmp(dictW[line_count], "references")==0) cwREFERENCES=line_count;
		else if (cwBIBLIOGRAPHY==0 && strcmp(dictW[line_count], "bibliography")==0) cwBIBLIOGRAPHY=line_count;

		else if (cwIS==0 && strcmp(dictW[line_count], "is")==0) cwIS=line_count;
		else if (cwWITH==0 && strcmp(dictW[line_count], "with")==0) cwWITH=line_count;
		else if (cwTHE==0 && strcmp(dictW[line_count], "the")==0) cwTHE=line_count;

		else if (cwON==0 && strcmp(dictW[line_count], "on")==0) cwON=line_count;
		else if (cwIN==0 && strcmp(dictW[line_count], "in")==0) cwIN=line_count;

		else if (cwWWW==0 && strcmp(dictW[line_count], "www")==0) cwWWW=line_count;
		else if (cwHTTP==0 && strcmp(dictW[line_count], "http")==0) cwHTTP=line_count;

		else if (cwISBN==0 && strcmp(dictW[line_count], "isbn")==0) cwISBN=line_count;

		line_count++;
	}
	free(s);
	printf("Loaded %d words\n",line_count);
	//printf("Loaded %d %d %d %d %d %d %d %d %d, %d %d %d, %d %d,  %d %d, %d\n", cwTEXT,cwNOWIKI,cwMATH,cwPRE,cwPAGE,cwIMAGE,cwCATEGORY,cwUSER,cwWIKIPEDIA ,cwIS,cwWITH,cwTHE,cwON,cwIN,cwWWW ,cwHTTP,cwISBN);
	sizeDict=line_count;
}

int DecodeCodeWord(int cw)
{
	int i=0;
	int c=cw&255;
	if (codeword2sym[c]<dict1size)
	{
		i=codeword2sym[c];
		return i;
	}

	i=dict1size*(codeword2sym[c]-dict1size);
	c=(cw>>8)&255;
	if(codeword2sym[c]<dict1size)
	{
		i+=codeword2sym[c];
		return i+dict1size;
	}

	i=(i-dict12size)*dict2size;
	i+=dict1size*(codeword2sym[c]-dict1size);

	c=(cw>>16)&255;
	i+=codeword2sym[c];
	return i+80*49;
}
void ReadDictionary()
{
	FILE *f=fopen("Data/english.dic","rb");
	LoadDictionary(f);
	fclose(f);
	for (int c=0; c<256; c++){codeword2sym[c]=0;}
	int charsUsed=0;
	for (int c=128; c<256; c++){codeword2sym[c]=charsUsed;charsUsed++;}
}
U32 lastCW=0;
void decodeWord(int c) {
        lastCW=DecodeCodeWord(c);
        assert(lastCW>=0 && lastCW<44515);
}
/*End dictionary*/
size_t GetFileSize(char *fileName)
{
	FILE *fp = fopen(fileName, "rb");
	assert(fp != NULL);
	fseek(fp, 0L, SEEK_END);
	size_t currentFileSize = ftell(fp);rewind(fp);
	fclose(fp);
	return currentFileSize;
}

unsigned char *LoadData(char *fileName, size_t *fileSizeHolder)
{
	size_t fileSize = GetFileSize(fileName);
	FILE *fp = fopen(fileName, "rb");assert(fp != NULL);
	int fileNumber = fileno(fp);
	unsigned char *fileData = mmap(NULL,fileSize, PROT_READ | PROT_WRITE, MAP_PRIVATE, fileNumber, 0);
	assert(fileData != MAP_FAILED);
	fclose(fp);
	*fileSizeHolder = fileSize;
	return fileData;
}
#define CacheSize 32  // (1<<5)
typedef struct
{
	uint32_t Name;
	uint32_t Value;
	uint32_t Length;
}XMLAttribute;
typedef struct
{
	uint32_t Data;
	uint32_t Length;
	uint32_t Type;
}XMLContent;
typedef struct
{
	XMLAttribute Items[4];
	uint32_t Index;
}XMLAttributes;
typedef struct
{
	uint32_t Name;
	uint32_t Length;
	int Level;
	int EndTag;     // 0 = false, 1 = true
	int Empty;      // 0 = false, 1 = true
	XMLContent Content;
	XMLAttributes Attributes;
}XMLTag;

typedef struct
{
	XMLTag Tags[CacheSize];
	uint32_t Index;
}XMLTagCache;
enum ContentFlags
{
	xText        = 0x001,
	xNumber      = 0x002,
	xDate        = 0x004,
	xTime        = 0x008,
	xURL         = 0x010,
	xLink        = 0x020,
	xCoordinates = 0x040,
	xTemperature = 0x080,
	xISBN        = 0x100
};
typedef enum XMLState
{
	xNone               = 0,
	xReadTagName        = 1,
	xReadTag            = 2,
	xReadAttributeName  = 3,
	xReadAttributeValue = 4,
	xReadContent        = 5,
	xReadCDATA          = 6,
	xReadComment        = 7
}XMLState;
const char* StateName(int state)
{
	switch (state)
	{
		case 0: return "xNone";
		case 1: return "xReadTagName";
		case 2: return "xReadTag";
		case 3: return "xReadAttributeName";
		case 4: return "xReadAttributeValue";
		case 5: return "xReadContent";
		case 6: return "xReadCDATA";
		case 7: return "xReadComment";
		default: return "unknown";
	}
}
bool isXML = false;
XMLState state = xNone;
XMLState pState = xNone;
U32 lastState = 0;      // Last position we were in XML
U32 last8Bytes = 0;     // Last 8 bytes
U32 WhiteSpaceRun = 0;
U32 pWSRun = 0;
U32 IndentTab = 0;
U32 IndentStep = 2;
U32 LineEnding = 2;
U32 StateBH[8] = {0};
XMLTagCache cache;
int bufferPosition = 0;  // Current byte position
U8 buffer[1024];        // Ring buffer for buf()

//Get byte from ring buffer
int buf(int offset){return buffer[(bufferPosition - offset) & 1023];}
//Get byte at absolute position
int bufr(int index){return buffer[index & 1023];}
//Simple hash function
U32 hash(U32 a, U32 b, U32 c){U32 h = a * 110002499u + b * 30005491u + c * 50004239u;return h ^ (h >> 9) ^ (a >> 3) ^ (b >> 3) ^ (c >> 4);}

void XMLModel_Init(void) 
{
	state = xNone;
	pState = xNone;
	WhiteSpaceRun = 0;
	pWSRun = 0;
	IndentTab = 0;
	IndentStep = 2;
	LineEnding = 2;
	lastState = 0;
	isXML = false;
	memset(StateBH, 0, sizeof(StateBH));
	memset(&cache, 0, sizeof(XMLTagCache));
	memset(buffer, 0, sizeof(buffer));
	bufferPosition = 0;
}
void XMLModel_Reset(void)
{
	state = xNone;
	pState = xNone;
	WhiteSpaceRun = 0;
	pWSRun = 0;
	IndentTab = 0;
	IndentStep = 2;
	LineEnding = 2;
	lastState = 0;
	memset(StateBH, 0, sizeof(StateBH));
}

int XML_Model(U8 currentByte, int partialByte, int last4Bytes, int bytePosition)
{
	U8 B = currentByte;
	XMLTag* pTag = &cache.Tags[(cache.Index - 1) & (CacheSize - 1)];
	XMLTag* Tag = &cache.Tags[cache.Index & (CacheSize - 1)];
	XMLAttribute* Attribute = &Tag->Attributes.Items[Tag->Attributes.Index & 3];
	XMLContent* Content = &Tag->Content;
	last8Bytes = (last8Bytes << 8) | buf(5);
	pState = state;
	//Track whitespace
	if((B == 0x09 || B == 0x20) && (B == (U8)((last4Bytes >> 8) & 0xFF) || !WhiteSpaceRun))
	{
		WhiteSpaceRun++;
		IndentTab = (B == 0x09);
	}
	else
	{
		if((state == xNone || (state == xReadContent && Content->Length <= LineEnding + WhiteSpaceRun)) && WhiteSpaceRun > 1 + IndentTab && WhiteSpaceRun != pWSRun)
		{
			IndentStep = abs((int)(WhiteSpaceRun - pWSRun));
			pWSRun = WhiteSpaceRun;
		}
		WhiteSpaceRun = 0;
	}
	if(B == 0x0A){LineEnding = 1 + (((U8)((last4Bytes >> 8) & 0xFF)) == 0x0D);}
	if(state != xNone){lastState = bytePosition;}
	switch(state) 
	{
		case xNone:
			if(B == '<')
			{
				state = xReadTagName;
				memset(Tag, 0, sizeof(XMLTag));
				if(pTag->EndTag || pTag->Empty)
				{
					Tag->Level = pTag->Level;
				}
				else
				{
					Tag->Level = pTag->Level + 1;
				}
				if(Tag->Level > 1)
				{
					//DetectContent(last4Bytes, last8Bytes, Content, B);
				}
			}
			break;
		case xReadTagName:
			if(Tag->Length > 0 && (B == 0x09 || B == 0x0A || B == 0x0D || B == 0x20)){state = xReadTag;}
			else if((B > 127) || (B == ':' || B == '@' || B == '_' || (B >= 'a' && B <= 'z')) || (Tag->Length > 0 && (B == '-' || B == '.' || (B >= '0' && B <= '9'))))
			{
				Tag->Length++;Tag->Name = Tag->Name * 263 * 32 + (B & 0xDF);
			}
			else if(B == '>')
			{
				if(Tag->EndTag){state = xNone;cache.Index++;}
				else{state = xReadContent;}
			}
			else if(B != '!' && B != '-' && B != '/' && B != '[')
			{
				state = xNone;cache.Index++;
			}
			else if(Tag->Length == 0)
			{
				if(B == '/')
				{
					Tag->EndTag = 1;
					if(Tag->Level > 0) Tag->Level--;	
				}
				else if(last4Bytes == ('<' * 256 * 256 * 256 + 0x212D2D))
				{
					state = xReadComment;
					if (Tag->Level > 0) Tag->Level--;
				}
			}
			break;
		case xReadTag:
			if(B == '/')
			{
				Tag->Empty = 1;
			}
			else if(B == '>')
			{
				if(Tag->Empty)
				{
					state = xNone;
					cache.Index++;
				}
				else
				{
					state = xReadContent;
				}
			}
			else if(B != 0x09 && B != 0x0A && B != 0x0D && B != 0x20)
			{
				state = xReadAttributeName;
				Attribute->Name = B;
			}
			break;
		case xReadAttributeName:
			if((last4Bytes & 0xFFF0) == ('=' * 256 + ' ') && (B == '"' || B == '\''))
			{
				state = xReadAttributeValue;
			}
			else if (B != '"' && B != '\'' && B != '=')
			{
				Attribute->Name = Attribute->Name * 263 * 32 + (B & 0xDF);
			}
			break;
	        case xReadAttributeValue:
	        	if(B == '"' || B == '\'')
	        	{
	        		Tag->Attributes.Index++;
	        		state = xReadTag;
	        	}
	        	else
	        	{
	        		Attribute->Value = Attribute->Value * 263 * 32 + B;
	        		Attribute->Length++;
	        	}
	        	break;
	        case xReadContent:
	       	if(B == '<')
	        	{
	        		state = xReadTagName;
	        		cache.Index++;
	        		memset(&cache.Tags[cache.Index & (CacheSize - 1)], 0, sizeof(XMLTag));
	        		cache.Tags[cache.Index & (CacheSize - 1)].Level = Tag->Level + 1;
	        	}
	        	else
	        	{
	        		Content->Length++;
	        		Content->Data = Content->Data * 997 * 16 + B;
	        		//DetectContent(last4Bytes, last8Bytes, Content, B);
	        	}
	        	break;
		case xReadComment:
			if((last4Bytes & 0xFFFFFF) == (0x2D2D00 + '>'))
			{
				state = xNone;
				cache.Index++;
			}
			break;
		default:
			break;
	}
	StateBH[state] = (StateBH[state] << 8) | B;
	isXML = (bytePosition - lastState) < 64;
	// Return context (simplified)
	U8 s = ((StateBH[state] >> (28)) & 0x08) |
	((StateBH[state] >> (21)) & 0x04) |
	((StateBH[state] >> (14)) & 0x02) |
	((StateBH[state] >> (7)) & 0x01) |
	(0 << 4);  // bpos placeholder
	return (s << 3) | state;
}

void TestParseXML(size_t fileSize, size_t fileIndex, unsigned char *data)
{
	XMLModel_Init();
	int partialByte = 1;int last4Bytes  = 0;int bitPosition = 0;int bytePosition= 0;
	int toProcess = 2000;
	for(int i = 0; i < toProcess; i++)
	{
		unsigned char B = data[i];
		bufferPosition += 1;
		bytePosition   += 1;
		last4Bytes = (last4Bytes << 8) | B;
		buffer[bufferPosition & 1023] = B;
		int context = XML_Model(B, partialByte, last4Bytes, bytePosition);
		if(isXML)
		{
			printf("isXML: Byte %4u: '%c' (0x%02X)  (state=%d: %s\n", i, isprint(B) ? B : '.', B, state, StateName(state));
		}
		else
		{
			if(B == '<' || B == '>')
			{
				printf("NotXML: Byte %4u: '%c' (0x%02X) → isXML = false (state=%d: %s)\n", i, B, B, state, StateName(state));
			}
		}
	}
}

int main()
{
	char *fileName = "Data/enwik8";
	size_t fileSize = 0;
	unsigned char *data = LoadData(fileName, &fileSize); 
	
	ReadDictionary();
	TestParseXML(fileSize, 0, data);
	assert(munmap(data, fileSize) != -1);
	return 0;
}