/*
   StoneCracker S404 algorithm data decompression routine
   (c) 2006 Jouni 'Mr.Spiv' Korhonen. The code is in public domain.
*/

//#include <stdio.h>
//#include <stdlib.h>
#include <string.h>

#include "Loaders.h"
#include "Song.h"

struct bitstream
{
	// bit buffer for rolling data bit by bit from the compressed file
	uint32_t       word;
	// bits left in the bit buffer
	uint32_t       left;
	// compressed data source
	const uint8_t* src;
	const uint8_t* orgsrc;
};

static int initGetb(struct bitstream* bs, const uint8_t* src, uint32_t src_length)
{
	int eff;

	bs->src = src + src_length;
	bs->orgsrc = src;

	bs->left = (bs->src[0] << 8) | bs->src[1]; // bit counter
//	if (bs->left & (~0xf))
//		fprintf(stderr, "Workarounded an ancient stc bug\n");
	// mask off any corrupt bits
	bs->left &= 0x000f;
	bs->src -= 2;

	// get the first 16-bits of the compressed stream
	bs->word = (bs->src[0] << 8) | bs->src[1];
	bs->src -= 2;

	eff = (bs->src[0] << 8) | bs->src[1]; // efficiency
	bs->src -= 2;

	return eff;
}

// get nbits from the compressed stream
static uint32_t getb(struct bitstream* bs, int nbits)
{
	bs->word &= 0x0000ffff;

	// If not enough bits in the bit buffer, get more
	if ((bs->left < nbits) && (bs->src >= bs->orgsrc))
	{
		bs->word <<= bs->left;
//		assert((bs->word & 0x0000ffffU) == 0);

		// Check that we don't go out of bounds
//		assert((uint8_t*) bs->src >= bs->orgsrc);

		bs->word |= (bs->src[0] << 8) | bs->src[1];
		bs->src-=2;

		nbits -= bs->left;
		bs->left = 16; // 16 unused (and some used) bits left in the word
	}

	// Shift nbits off the word and return them
	bs->left -= nbits;
	bs->word <<= nbits;

	return bs->word >> 16;
}

const _kernel_oserror* Decomp_S404(SongHdr* pSong)
{
	const _kernel_oserror* e = NULL;
	char tag[4];
	uint32_t outSize, inSize, secSize;
	uint8_t* pSrc = NULL;
	uint32_t w;
	int32_t eff;
	int32_t n;
	uint8_t* dst;
	uint8_t* dstend;
	int32_t oLen;
	struct bitstream bs;

	e = FileLoad_ReadInt(pSong, (uint32_t*) tag, 4);
	if (e) return e;

	if (memcmp(tag, "S404", 4) != 0)
		return Loaders_NotThisType;

	e = FileLoad_ReadReverseInt(pSong, &secSize, 4);
	if (!e) e = FileLoad_ReadReverseInt(pSong, &outSize, 4);
	if (!e) e = FileLoad_ReadReverseInt(pSong, &inSize, 4);
	if (e) return e;

	e = Loaders_Alloc(pSong, (void**) &pSong->pLoaderData->Decomp.pMemory, outSize);
	if (e) return e;
	pSong->pLoaderData->Decomp.MemSize = outSize;

	e = Loaders_Alloc(pSong, (void**) &pSrc, inSize + 2);
	if (e) return e;
	e = FileLoad_Read(pSong, pSrc, inSize + 2);
	if (e) return e;

	oLen = outSize;
	dstend = dst = pSong->pLoaderData->Decomp.pMemory + oLen;

	eff = initGetb(&bs, pSrc, inSize);

	while (oLen > 0)
	{
		w = getb(&bs, 9);

		if (w < 0x100)
		{
			*--dst = w;
			oLen--;
		}
		else if (w == 0x13e || w == 0x13f)
		{
			w <<= 4;
			w |= getb(&bs, 4);

			n = (w & 0x1f) + 14;
			if (oLen < n)
			{
				// It happens with some files
				n = oLen;
			}
			oLen -= n;
			while (n-- > 0)
			{
				w = getb(&bs, 8);
				*--dst = w;
			}
		}
		else
		{
			if (w >= 0x180)
			{
				// copy 2-3
				n = w & 0x40 ? 3 : 2;

				if (w & 0x20)
				{
					// dist 545 ->
					w = (w & 0x1f) << (eff - 5);
					w |= getb(&bs, eff - 5);
					w += 544;
				}
				else if (w & 0x30)
				{
					// dist 1 -> 32
					w = (w & 0x0f) << 1;
					w |= getb(&bs, 1);
				}
				else
				{
					// dist 33 -> 544
					w = (w & 0x0f) << 5;
					w |= getb(&bs, 5);
					w += 32;
				}
			}
			else if (w >= 0x140)
			{
				// copy 4-7
				n = ((w & 0x30) >> 4) + 4;

				if (w & 0x08)
				{
					// dist 545 ->
					w = (w & 0x07) << (eff - 3);
					w |= getb(&bs, eff - 3);
					w += 544;
				}
				else if (w & 0x0c)
				{
					// dist 1 -> 32
					w = (w & 0x03) << 3;
					w |= getb(&bs, 3);
				}
				else
				{
					// dist 33 -> 544
					w = (w & 0x03) << 7;
					w |= getb(&bs, 7);
					w += 32;
				}
			}
			else if (w >= 0x120)
			{
				// copy 8-22
				n = ((w & 0x1e) >> 1) + 8;

				if (w & 0x01)
				{
					// dist 545 ->
					w = getb(&bs, eff);
					w += 544;
				}
				else
				{
					w = getb(&bs, 6);

					if (w & 0x20)
					{
						// dist 1 -> 32
						w &= 0x1f;
					}
					else
					{
						// dist 33 -> 544
						w <<= 4;
						w |= getb(&bs, 4);
						w += 32;
					}
				}
			}
			else
			{
				w = (w & 0x1f) << 3;
				w |= getb(&bs, 3);
				n = 23;

				while (w == 0xff)
				{
					n += w;
					w = getb(&bs, 8);
				}
				n += w;

				w = getb(&bs, 7);

				if (w & 0x40)
				{
					// dist 545 ->
					w = (w & 0x3f) << (eff - 6);
					w |= getb(&bs, eff - 6);
					w += 544;
				}
				else if (w & 0x20)
				{
					// dist 1 -> 32
					w &= 0x1f;
				}
				else
				{
					// dist 33 -> 544;
					w <<= 4;
					w |= getb(&bs, 4);
					w += 32;
				}
			}

			if (oLen < n)
			{
				// It happens with some files
				n = oLen;
			}
			oLen -= n;
			if ((dst + w + 1) >= dstend)
			{
				e = Loaders_Error(pSong, 0, "S404: Copying from too high memory, %d", w);
				goto decomp_error;
			}

			while (n-- > 0)
			{
				dst--;
				// assert((dst + w + 1) < (orgdst + dst_length));
				*dst = dst[w + 1];
			}
		}
	}

decomp_error:
	Loaders_Free(pSong, pSrc);

	return e;
}
