#include <string.h>
#include "Song.h"
#include "Effects.h"
#include "Instrument.h"
#include "Loaders.h"
#include "FSysLog.h"

/*
 * Channels: [1...32]
 * Patterns: [1...1024]
 * Rows    : [1...512]
 * Orders  : [1...65535]
 * Samples : [1...255]
 * Instr.  : [0...255]
 * Tempo   : [3...256], row duration is T/4 seconds. Set directly or calculated = (BPM/60 * RPB)*4.
 * BPM     : [1...255], beats per minutes.
 * RPB     : [1...15], rows per beat.
 * Speed   : Autocalculated, but irrelevant since no effects depend on it.
 * Notes   : [C-0...C-3...B-8]
 * Pitch   : Uses semitones, value is upped by 12 each octave up.
 *           Slides in x/16 units per row.
 * Volume  : [0...255], linear.
 * Panning : [0...255].
 * Sampling: 8364 Hz (frequency is turned into a relative tone).
 *
 * Notes:
 * There is no loop effect so we will force TimPlayer's max rows limit from 256 to 512
 * to cope with a few existing files.
 *
 * The row tempo is in turn automatically translated into a number of frames
 * and from there we have tempo = DMF tempo * frames.
 *
 * Speed (frames per row) is not a variable but a function of the tempo.
 *
 * How is the notion of frames used in the effects:
 * - Arpeggio?
 * - Slides (+Scratch to note): the effect specifies the delta (value) at the end of the row
 *   and the tracker divides it by the speed to smooth it out frame by frame.
 * - Delay, retrig, tremor and note cut: specify intervals in 1/16th or 1/256th of a row,
 *   not in number of frames.
 * - Vibrato/Tremolo/Panbrello define not a speed but a period in number rows.
 *
 * Implementation:
 * Since except for Arpeggio the notion of speed/frames is irrelevant, we will make it a whole
 * lot easier for us in the implementation of effects by using a fixed speed of 16.
 */

#define NoteDelta (Note_Central-12*3)

#define TAG(x) (*(const uint32_t*) Tag_##x)

static const uint8_t Tag_DMDL[] = "DDMF";
static const uint8_t Tag_INFO[] = "INFO";
static const uint8_t Tag_CMSG[] = "CMSG";
static const uint8_t Tag_SEQU[] = "SEQU";
static const uint8_t Tag_PATT[] = "PATT";
static const uint8_t Tag_INST[] = "INST";
static const uint8_t Tag_SMPI[] = "SMPI";
static const uint8_t Tag_SMPD[] = "SMPD";
static const uint8_t Tag_CRAP[] = "\xE4\x9D\x21\x9C";
static const uint8_t Typestr_DMF[] = "X-Tracker";
static const char Invalid_Block[] = "Invalid block";
static const char Unexpected_Block[] = "Block not expected in that position";

typedef struct
{
	uint32_t    Tag;
	uint8_t     Version;
	uint8_t     Tracker[8];
	uint8_t     Name[30];
	uint8_t     Author[20];
	uint8_t     Date[3];
} LHdr;

typedef struct
{
	uint32_t	BPM;
	uint32_t	RPB;
	uint32_t	DMFtempo;
	uint32_t	speed;
	uint32_t	tempo;
} LTempo;

/*
// A DMF row speed in 1/4 Hz tanslates in an autocalculated speed and from there the real tempo
static void convert_tickspeed(LTempo* ptempo)
{
	static const uint8_t limits[7] = {4,8,16,31,58,104,172};
	int shift = 0;

	if (ptempo->BPM && ptempo->RPB)
		ptempo->DMFtempo = (ptempo->BPM * ptempo->RPB) / 15;

	if (ptempo->DMFtempo < 3) ptempo->DMFtempo = 3;

	for (;shift < 7; shift++)
		if (ptempo->DMFtempo < limits[shift]) break;

	ptempo->speed =  1 + (1 << (7 - shift));
	ptempo->tempo = ptempo->DMFtempo * ptempo->speed; // in 1/4 Hz
}
*/
static void convert_glbeffect(SongHdr* pSong, uint32_t effect, uint32_t value)
{
	uint32_t oeffect = 0x100 | effect;
#ifdef USELOG
	uint32_t ovalue = value;
#endif

	switch(effect)
	{
		case 1: // Set tempo in 1/4 Hz unit, 255 is 64 rows per sec
		{
			value = (1 + value) * 16; // cf. rows to frames
			if (value <= 0xfff)
				Pattern_AddGlbEffect_Tempo(pSong, cmd_set, value);
			else
				Pattern_AddGlbEffect_Tempo(pSong, gcmd_tempo_setlarge, value >> 4);
		}
		break;
		case 2: // Set BPM, 0 switch to tick speed
		{
			Pattern_AddGlbEffect_Tempo(pSong, gcmd_tempo_BPM, value);
		}
		break;
		case 3: // Set RPB: xy x is RPB, y is reserved, x=0 switch to tick speed
		{
			if (value) Pattern_AddGlbEffect_Tempo(pSong, gcmd_tempo_TPB, value * 16); // cf. rows to frames
		}
		break;
		case 4: // Global: Delay row for x/16 rows
		{
			Pattern_AddGlbEffect_Frames(pSong, gcmd_frames_delay, value);
		}
		break;
		case 5: // External sync
		{
			// Ignored
		}
		break;
		case 6: // DMF tempo/BPM up
		{
			Pattern_AddGlbEffect_Tempo(pSong, cmd_up + flag_cmd_slide_frame0, value);
		}
		break;
		case 7: // DMF tempo/BPM down
		{
			Pattern_AddGlbEffect_Tempo(pSong, cmd_down + flag_cmd_slide_frame0, value);
		}
		break;
		default:
		{
			if (oeffect) SysLog_BadEffect(pSong, 0, oeffect, ovalue);
		}
	}
}

// Convert from period in nr of rows into a vibrato speed (x steps per frame)
// Valid output range is [1, 15].
static inline int convert_vibrato_period(uint32_t rows)
{
	rows++;
	if (rows < 2) return 15;

	// cf period is 256 steps = frames * rows = 16 * rows
	return 16 / rows;
}

static void convert_insteffect(SongHdr* pSong, uint32_t effect, uint32_t value, uint32_t note)
{
	uint32_t oeffect = 0x200 | effect;
#ifdef USELOG
	uint32_t ovalue = value;
#endif

	switch(effect)
	{
		case 1: // Note: Cut note
		{
			Pattern_AddEffect_NoteVolume(pSong, cmd_volume_cut, 0);
		}
		break;
		case 2: // Note: Loop off
		{
			Pattern_AddEffect_Instrument(pSong, cmd_sample_loop_off, 0);
		}
		break;
		case 3: // Note: Restart note and restore note volume
		{
			Pattern_AddEffect_RetrigCounter(pSong, cmd_retrig_count_type_MOD, 0xff);
			Pattern_AddEffect_Instrument(pSong, cmd_sample_note_retrig, 8);
		}
		break;
		case 4: // Note: Delay for x/256 row
		{
			Pattern_AddEffect_Instrument(pSong, cmd_sample_note_delay, 1 + (value >> 4));
		}
		break;
		case 5: // Note: Retrig every x/256 row
		{
			value = 1 + (value >> 4);
			Pattern_AddEffect_RetrigCounter(pSong, cmd_retrig_count_type_MOD, value);
			Pattern_AddEffect_Instrument(pSong, cmd_sample_note_retrig, 8);
		}
		break;
		case 9: // Note: Set sample offset + 192K
			value += 256;
		// nobreak;
		case 8: // Note: Set sample offset + 128K
			value += 256;
		// nobreak;
		case 7: // Note: Set sample offset + 64K
			value += 256;
		// nobreak;
		case 6: // Note: Set sample offset
		{
			// define offset
			Pattern_AddEffect_Instrument(pSong, cmd_sample_set_offset, 0x000 | 0);
			// set offset byte 1
			Pattern_AddEffect_Instrument(pSong, cmd_sample_set_offset, 0x100 | (value & 0xff));
			// set offset byte 2
			Pattern_AddEffect_Instrument(pSong, cmd_sample_set_offset, 0x200 | (value >> 8));

			// only if a note is defined at the same time
			if (note) Pattern_AddEffect_Instrument(pSong, cmd_sample_set_offset, 0xf00);
		}
		break;
/* Older version of the doc mention revert sample direction in 7 and rewind sample in 8 */
		case 10: // Note, reverse direction
		{
			Pattern_AddEffect_Instrument(pSong, cmd_sample_reverse_play, 0);
		}
		break;
		default:
		{
			if (oeffect) SysLog_BadEffect(pSong, 0, oeffect, ovalue);
		}
	}
}

static void convert_noteeffect(SongHdr* pSong, uint32_t effect, uint32_t value, uint32_t note)
{
	uint32_t oeffect = 0x300 | effect;
#ifdef USELOG
	uint32_t ovalue = value;
#endif

	switch(effect)
	{
		case 1: // Note: Set signed fine tune in 1/128 semitone
		{
			int32_t svalue = value << 24;
			// only if a note is defined at the same time
			if (note) Pattern_AddEffect_Instrument(pSong, cmd_sample_set_finetune, svalue >> 23);
		}
		break;
		case 2: // Note: Delay for x/256 row
		{
			Pattern_AddEffect_Instrument(pSong, cmd_sample_note_delay, 1 + (value >> 4));
		}
		break;
		case 3: // Pitch: Arpeggio
		{
			uint32_t val;

			val = value >> 4;
			value &= 0xf;

			Pattern_AddEffect_Arpeggio(pSong, value, val, cmd_arpeggio_type_NHL);
		}
		break;
		case 4: // Pitch: Smoothed up by x/16 seminotes
		{
			uint32_t val;

			value <<= 2;
			val = value >> 4;
			value &= 0xf;
			if (val)   Pattern_AddEffect_Pitch(pSong, cmd_up | flag_cmd_slide_frame0N0, val);
			if (value) Pattern_AddEffect_Pitch(pSong, cmd_up | flag_cmd_slide_frame0, value);
		}
		break;
		case 5: // Pitch: Smoothed down by x/16 seminotes
		{
			uint32_t val;

			value <<= 2;
			val = value >> 4;
			value &= 0xf;
			if (val)   Pattern_AddEffect_Pitch(pSong, cmd_down | flag_cmd_slide_frame0N0, val);
			if (value) Pattern_AddEffect_Pitch(pSong, cmd_down | flag_cmd_slide_frame0, value);
		}
		break;
		case 6: // Pitch: Smoothed Portamento
		{
			uint32_t val;

			value <<= 2;
			val = value >> 4;
			value &= 0xf;
			if (val)   Pattern_AddEffect_Pitch(pSong, cmd_portamento + flag_cmd_slide_frame0N0, val);
			if (value) Pattern_AddEffect_Pitch(pSong, cmd_portamento + flag_cmd_slide_frame0, value);
		}
		break;
		case 7: // Pitch: Scratch to Note (at end of row)
		{
			if (value < 108) Pattern_AddEffect_Pitch(pSong, cmd_set, value + NoteDelta);
			else SysLog_BadEffectValue(pSong, 0, oeffect, ovalue);
		}
		break;
		case 8: // Pitch: Vibrato Sin with period of x rows and amplitude of y/8 semitone
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = 1 + (value & 0xf);
			value <<= 3;
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_type, vibrato_type_sin);
			if (speed) Pattern_AddEffect_Pitch(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 9: // Pitch: Vibrato Saw with period of x rows and amplitude of y/8 semitone
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = 1 + (value & 0xf);
			value <<= 3;
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_type, vibrato_type_saw);
			if (speed) Pattern_AddEffect_Pitch(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 10: // Pitch: Vibrato Square with period of x rows and amplitude of y/8 semitone
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = 1 + (value & 0xf);
			value <<= 3;
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_type, vibrato_type_square);
			if (speed) Pattern_AddEffect_Pitch(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_Pitch(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 11: // Volume: Tremor xy in (x+1)/32 row and (y+1)/32 row
		{
			uint32_t val;

			val = 1 + (value >> 4);
			val >>= 1;
			if (!val) val = 1;
			value = 1 + (value & 0xf);
			value >>= 1;
			if (!value) value = 1;
			Pattern_AddEffect_NoteVolume(pSong, cmd_volume_tremor_S3M, Effect_Tremor(value, val));
		}
		break;
		case 12: // Note: Cut note after x/256 row
		{
			Pattern_AddEffect_NoteVolume(pSong, cmd_volume_cut, value >> 4);
		}
		break;
		default:
		{
			if (oeffect) SysLog_BadEffect(pSong, 0, oeffect, ovalue);
		}
	}
}

static void convert_voleffect(SongHdr* pSong, uint32_t effect, uint32_t value, uint32_t note)
{
	uint32_t oeffect = 0x400 | effect;
#ifdef USELOG
	uint32_t ovalue = value;
#endif
	IGNORE(note);

	switch(effect)
	{
		case 1: // Volume: Smoothed up
		{
			uint32_t val;

			val = value >> 4;
			value &= 0xf;
			if (val)   Pattern_AddEffect_NoteVolume(pSong, cmd_up | flag_cmd_slide_frame0N0, val);
			if (value) Pattern_AddEffect_NoteVolume(pSong, cmd_up | flag_cmd_slide_frame0, value);
		}
		break;
		case 2: // Volume: Smoothed down
		{
			uint32_t val;

			val = value >> 4;
			value &= 0xf;
			if (val)   Pattern_AddEffect_NoteVolume(pSong, cmd_down | flag_cmd_slide_frame0N0, val);
			if (value) Pattern_AddEffect_NoteVolume(pSong, cmd_down | flag_cmd_slide_frame0, value);
		}
		break;
		case 3: // Volume: Tremor xy in (x+1)/32 row and (y+1)/32 row
		{
			uint32_t val;

			val = 1 + (value >> 4);
			val >>= 1;
			if (!val) val = 1;
			value = 1 + (value & 0xf);
			value >>= 1;
			if (!value) value = 1;
			Pattern_AddEffect_NoteVolume(pSong, cmd_volume_tremor_S3M, Effect_Tremor(value, val));
		}
		break;
		case 4: // Volume: Vibrato Sin (15 = full volume range, from mid of actual volume)
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = (1 + (value & 0xf)) << 3; // act as if actual volume = 256
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_type, vibrato_type_sin);
			if (speed) Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 5: // Volume: Vibrato Saw
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = (1 + (value & 0xf)) << 3; // act as if actual volume = 256
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_type, vibrato_type_saw);
			if (speed) Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 6: // Volume: Vibrato Square
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = (1 + (value & 0xf)) << 3; // act as if actual volume = 256
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_type, vibrato_type_square);
			if (speed) Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_NoteVolume(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		case 7: // Panning: Set
		{
			if (value >= 128) value++;
			Pattern_AddEffect_Panning(pSong, cmd_set, value);
		}
		break;
		case 8: // Panning: Smoothed left
		{
			Pattern_AddEffect_Panning(pSong, cmd_down | flag_cmd_slide_frame0, value);
		}
		break;
		case 9: // Panning: Smoothed right
		{
			Pattern_AddEffect_Panning(pSong, cmd_up | flag_cmd_slide_frame0, value);
		}
		break;
		case 10: // Panning: Vibrato Sin (15 = full range, I assume from centre)
		{
			uint32_t speed = convert_vibrato_period(value >> 4);
			value = (1 + (value & 0xf)) << 3;
			Pattern_AddEffect_Panning(pSong, cmd_vibrato_type, vibrato_type_sin);
			if (speed) Pattern_AddEffect_Panning(pSong, cmd_vibrato_speed, speed << 2);
			Pattern_AddEffect_Panning(pSong, cmd_vibrato_depth | flag_cmd_vibrato_frameN0, value);
		}
		break;
		default:
		{
			if (oeffect) SysLog_BadEffect(pSong, 0, oeffect, ovalue);
		}
	}
}

static const _kernel_oserror* Pattern_Decode
   ( SongHdr* pSong
   , uint32_t i
   , Pattern* pPattern
   , uint32_t channels
   , uint32_t beat
   , const uint8_t* pStart
   , const uint8_t* pEnd
   )
{
	const _kernel_oserror* err = NULL;
	int             j, k, Note, Inst, Effect, Value, Info;
	const uint8_t*  pEnd2;
	uint32_t        counter[32] = { 0, 0, 0, 0, 0, 0, 0, 0
	                              , 0, 0, 0, 0, 0, 0, 0, 0
	                              , 0, 0, 0, 0, 0, 0, 0, 0
	                              , 0, 0, 0, 0, 0, 0, 0, 0};
	uint32_t        glbcounter = 0;

	err = Loaders_StartPattern(pSong, i);
	if (err) return err;

	for (j = 0; j < pPattern->Rows; j++)
	{
		err = Loaders_StartRow(pSong, j);
		if (err) return err;

		// Beat info must be inserted at start of first row?
		if (!j && (beat >> 4))
			Pattern_AddGlbEffect_Tempo(pSong, gcmd_tempo_TPB, (beat >> 4) * 16); // cf. rows to frames

		// Read global effect
		if (glbcounter == 0)
		{
			if (pStart > pEnd + 2)
				SysLog_FileCorrupted(SysLog_High, pSong, 0, "Pattern %d, to short", i);
			else
			{
				Info = *pStart++;
				if (Info & 0x80) glbcounter =  *pStart++;
				Effect = Info & 0x3f;
				if (Effect)
				{
					Value = *pStart++;
					convert_glbeffect(pSong, Effect, Value);
				}
			}
		}
		else
			glbcounter--;

		for (k = 0; k < channels; k++)
		{
			if (counter[k])
			{
				counter[k]--;
				continue;
			}
			if (pStart < pEnd)
			{
				Info = *pStart++;
				pEnd2 = pStart;
				if (Info & 0x80) pEnd2++;
				if (Info & 0x40) pEnd2++;
				if (Info & 0x20) pEnd2++;
				if (Info & 0x10) pEnd2++;
				if (Info & 8) pEnd2+=2;
				if (Info & 4) pEnd2+=2;
				if (Info & 2) pEnd2+=2;
			}
			else
			{
				pEnd2 = pStart;
				Info = 0;
			}

			if (pEnd2 > pEnd)
			{
				SysLog_FileCorrupted(SysLog_High, pSong, 0, "[%03x:%03x:%02x] Pattern to short", i, j, k);
				break;
			}

			if (Info)
			{
				if (Info & 0x80)
					counter[k] = *pStart++;
				if (Info & 0x40)
					Inst = *pStart++;
				else
					Inst = 0;
				if (Info & 0x20)
				{
					Note = *pStart++;
					if (Note == 255)
						Note = Note_Cut;
					else
					{
						// Note + 128 does trigger a note but sets mem
						// till a better solution is found handle it as normal note
						Note &= 0x7f;
						if (Note > 108)
						{
							SysLog_BadNote(pSong, 0, k, Note);
							Note = 0;
						}
						else if (Note)
							Note += NoteDelta - 1;
					}
				}
				else
					Note = 0;

				err = Loaders_StartChannel(pSong, k, Note, Inst);
				if (err) return err;

				if (Info & 0x10)
				{
					Value = *pStart++;
					if (Value) Pattern_AddEffect_NoteVolume(pSong, cmd_set, Value);
				}
				if (Note >= Note_CmdMin) Note = 0;
				if (Info & 0x08)
				{
					// Inst effect
					Effect = *pStart++;
					Value = *pStart++;
					convert_insteffect(pSong, Effect, Value, Note);
				}
				if (Info & 0x04)
				{
					// Note effect
					Effect = *pStart++;
					Value = *pStart++;
					convert_noteeffect(pSong, Effect, Value, Note);
				}
				if (Info & 0x02)
				{
					// Volume effect
					Effect = *pStart++;
					Value = *pStart++;
					convert_voleffect(pSong, Effect, Value, Note);
				}

				err = Loaders_EndChannel(pSong);
				if (err) return err;
			}
		}

		err = Loaders_EndRow(pSong);
		if (err) return err;
	}

	if (pStart < pEnd)
		SysLog_FileCorrupted(SysLog_High, pSong, 0, "Pattern %d, unused bytes %d", i, pEnd - pStart);

	return Loaders_EndPattern(pSong, pPattern);
}

typedef struct
{
	int32_t   left, right;
	uint8_t   value;
} node;

typedef struct
{
	uint8_t*  pCur;
	uint8_t*  pEnd;
	uint32_t  bitbuf;
	uint32_t  bitnum;
	uint32_t  nodecount;
	node      nodes[256];
} tree;

static uint8_t read_bits(tree* tree, int nbits)
{
	uint8_t x = 0, bitv = 1;

	while (nbits--)
	{
		if (tree->bitnum)
			tree->bitnum--;
		else
		{
			tree->bitbuf = (tree->pCur < tree->pEnd) ? *(tree->pCur++) : 0;
			tree->bitnum = 7;
		}
		if (tree->bitbuf & 1) x |= bitv;
		bitv <<= 1;
		tree->bitbuf >>= 1;
	}

	return x;
}

// tree: [8-bit value][12-bit index][12-bit index] = 32-bit
static void new_node(tree* tree)
{
	uint8_t isleft, isright;
	int     actnode;

	actnode = tree->nodecount;

	if (actnode > 255)
		return;

	tree->nodes[actnode].value = read_bits(tree, 7);
	isleft = read_bits(tree, 1);
	isright = read_bits(tree, 1);

	tree->nodecount++;

	if ((tree->nodecount > 255) && (isleft || isright))
	{
		SysLog_Log(SysLog_High, "Last Hufmann code should not have childs");
		isleft = 0;
		isright = 0;
	}

	if (isleft)
	{
		tree->nodes[actnode].left = tree->nodecount;
		new_node(tree);
	}
	else
		tree->nodes[actnode].left = -1;

	if (isright)
	{
		tree->nodes[actnode].right = tree->nodecount;
		new_node(tree);
	}
	else
		tree->nodes[actnode].right = -1;
}

static const _kernel_oserror* unpack(SongHdr* pSong, Sample* pSmp, uint8_t* pFromStart, uint8_t* pFromEnd)
{
	const _kernel_oserror* err = NULL;
	tree*     ptree;
	int       actnode;
	int       size;
	uint8_t   value, sign, delta = 0;
    uint8_t*  pToStart;
    uint8_t*  pToEnd;

	if (pSmp->Type & Smp_Type_16bit)
		size = pSmp->Size << 1;
	else
		size = pSmp->Size;

	err = Loaders_Alloc(pSong, (void**) &pSmp->Ptr, size + 4);
	if (!err) err = Loaders_Alloc(pSong, (void**) &ptree, sizeof(*ptree));
	if (err) return err;
    pToStart = pSmp->Ptr;
    pToEnd = pToStart + size;

	memset(ptree, 0, sizeof(*ptree));
	ptree->pCur = pFromStart;
	ptree->pEnd = pFromEnd;
	new_node(ptree);
	value = 0;

	while (pToStart < pToEnd)
	{
		actnode = 0;
		sign = read_bits(ptree, 1);

		do
		{
			if (read_bits(ptree, 1))
				actnode = ptree->nodes[actnode].right;
			else
				actnode = ptree->nodes[actnode].left;
			delta = ptree->nodes[actnode].value;
			if ((ptree->pCur >= ptree->pEnd) && (!ptree->bitnum)) break;
		} while ((ptree->nodes[actnode].left >= 0) && (ptree->nodes[actnode].right >= 0));

		if (sign)
			delta ^= 0xff;
		value += delta;
		*pToStart++ = value;
	}

	if (pToStart < pToEnd)
	{
		SysLog_FileCorrupted
			( SysLog_High, pSong, 0
			, "Packed sample %d truncated by %d bytes"
			, 1 + (pSmp - pSong->pSamples), pToEnd - pToStart
			);
		pSmp->Size = pToStart - (uint8_t*) pSmp->Ptr;
		if (pSmp->Type & Smp_Type_16bit)
			pSmp->Size >>= 1;
	}

	if (ptree->pCur < ptree->pEnd)
	{
		SysLog_Log
			( SysLog_High
			, "Packed sample %d, unused bytes %d"
			, 1 + (pSmp - pSong->pSamples), ptree->pEnd - ptree->pCur
			);
	}

	Loaders_Free(pSong, ptree);

	return NULL;
}

static const _kernel_oserror* Read_TagInfo(SongHdr* pSong, uint32_t* pTag, uint32_t* pTagSize)
{
	const _kernel_oserror* err = NULL;

	err = FileLoad_ReadInt(pSong, pTag, 4);
	if (err) return err;
	err = FileLoad_ReadInt(pSong, pTagSize, 4);

	return err;
}

const _kernel_oserror* Loader_DMF(SongHdr* pSong)
{
	const _kernel_oserror* err = NULL;
	SubSong*    pSubSong = Song_GetSubSong(pSong, 0);
	int         i, j, k;
	Pattern*    pPattern;
	Instrument* pInst;
	Sample*     pSmp;
	uint32_t    val;
	LHdr*       pLHdr = NULL;
	uint8_t*    pLData = NULL;
	uint32_t    FileSize, Tag, TagSize;
	uint32_t    FileOffset;

	err = Loaders_Alloc(pSong, (void**) &pLHdr, sizeof(*pLHdr));
	if (err) goto loader_err;

	FileSize = FileLoad_GetSize(pSong);

	// is it a DMF file?
	err = FileLoad_SetPos(pSong, 0);
	if (err) goto loader_err;
	err = FileLoad_Read(pSong, pLHdr, 0x42);
	if (err) goto loader_err;
	if (pLHdr->Tag != TAG(DMDL))
	{
		err = Loaders_NotThisType;
		goto loader_err;
	}

	pSong->Version = 100*pLHdr->Version;
	err = Loaders_String(pSong, &pSong->pName, &pLHdr->Name[0], sizeof(pLHdr->Name), false);
	if (!err) err = Loaders_String(pSong, &pSong->pAuthor, &pLHdr->Author[0], sizeof(pLHdr->Author), false);
	if (err) goto loader_err;

	pSong->Flags = Song_Flag_Linear;
	pSong->MinPitch = NoteDelta;
	pSong->MaxPitch = NoteDelta + 12 * 9 - 1;
	pSong->MinSpeed = 16;
	pSong->MaxSpeed = 16;
	pSong->TempoBase = Tempo_Base_4Hz;
	pSong->MinTempo = 3*16; // cf. rows to frames
	pSong->MaxTempo = 256*16; // cf. rows to frames
	pSubSong->Defaults.Speed = 16;
	pSubSong->Defaults.Tempo = 33*16; // cf. rows to frames

	// ... file type ptr
	pSong->pType = Typestr_DMF;

	// Read TAGS.
	// Rule: assume that when tags require information from another tag, this tag is stored
	// earlier in the tag sequence, but don't assume any fixed tag order.
	// We will thus reject files which break this rule as too badly corrupted.
	// For missing tags which don't impact others (pattern, sequence),
	// we will let the global inegrity check catch these cases.
	while (FileLoad_GetPos(pSong) < FileSize - 8)
	{
		// Read TAG id & size
		err = Read_TagInfo(pSong, &Tag, &TagSize);
		if (err) goto loader_err;

		FileOffset = FileLoad_GetPos(pSong);

		if (Tag == TAG(INFO))
		{
			// Nothing to do
		}
		else if (Tag == TAG(CMSG))
		{
			uint8_t* pc;

			if (pSong->pComments != NULL)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}
			// Skip one byte
			FileLoad_Skip(pSong, 1);

			val = TagSize - 1 + 39;
			pSong->CommentsLen = TagSize - 1 + (val / 40);
			err = Loaders_AllocString(pSong, (void**) &pSong->pComments, pSong->CommentsLen);
			if (err) goto loader_err;
			pc = pSong->pComments;
			for (i = 0; i < TagSize - 1; i += 40)
			{
				err = FileLoad_Read(pSong, pc, 40);
				if (err) goto loader_err;
				for(j = 0; j < 40; j++, pc++)
				{
					if (*pc < ' ') *pc = ' ';
				}
				*pc++ = '\n';
			}
			*pc = 0;
		}
		else if (Tag == TAG(SEQU))
		{
			if (pSubSong->SeqLen > 0)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}

			if (TagSize < 6)
			{
				err = Loaders_Error(pSong, -8, Invalid_Block);
				goto loader_err;
			}

			// Sequence loop start
			err = FileLoad_ReadInt(pSong, &val, 2);
			if (err) goto loader_err;
			pSubSong->RestartPos = val;
			// Sequence loop end
			err = FileLoad_ReadInt(pSong, &val, 2);
			if (err) goto loader_err;
			pSubSong->SeqLen = (TagSize - 4) / 2;

			if (!pSubSong->SeqLen)
			{
				err = Loaders_InvalidSong(pSong, -12, &pSubSong->SeqLen, pSubSong->SeqLen);
				goto loader_err;
			}

			// Read sequence
			err = Loaders_AllocSeq(pSong, pSubSong);
			if (err) goto loader_err;

			for (i = 0; i < pSubSong->SeqLen; i++)
			{
				err = FileLoad_ReadInt(pSong, &val, 2);
				if (err) goto loader_err;
				pSubSong->pSeqs[i] = val;
			}
		}
		else if (Tag == TAG(PATT))
		{
			if (pSong->Patterns > 0)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}

			err = FileLoad_ReadInt(pSong, &pSong->Patterns, 2);
			if (err) goto loader_err;

			if (!pSong->Patterns || (pSong->Patterns > 1024) || (pSong->Patterns > song_max_patterns))
			{
				err = Loaders_InvalidSong(pSong, -2, &pSong->Patterns, pSong->Patterns);
				goto loader_err;
			}

			err = FileLoad_ReadByte(pSong, &pSong->Channels);
			if (err) goto loader_err;
			if (!pSong->Channels || (pSong->Channels > 32))
			{
				err = Loaders_InvalidSong(pSong, -1, &pSong->Channels, pSong->Channels);
				goto loader_err;
			}

			for ( i = 0, pPattern = pSong->pPatterns; i < pSong->Patterns; i++, pPattern++)
			{
				uint32_t channels;
				uint32_t beat;
				uint32_t size;

				err = FileLoad_ReadByte(pSong, &channels);
				if (!err) err = FileLoad_ReadByte(pSong, &beat);
				if (!err) err = FileLoad_ReadInt(pSong, &pPattern->Rows, 2);
				if (!err) err = FileLoad_ReadInt(pSong, &size, 4);

				if (!channels || (channels > pSong->Channels))
				{
					err = Loaders_Error(pSong, -8, "Invalid nr of channels %d for pattern %d", channels, i);
					goto loader_err;
				}

				if (!pPattern->Rows || (pPattern->Rows > song_max_rows))
				{
					err = Loaders_InvalidSong(pSong, -6, &pPattern->Rows, pPattern->Rows);
					goto loader_err;
				}

				if (FileOffset + TagSize < FileLoad_GetPos(pSong) + size)
				{
					err = Loaders_Error(pSong, -4, "Block PATT to short");
					goto loader_err;
				}

				err = Loaders_Alloc(pSong, (void**) &pLData, size);
				if (!err) err = FileLoad_Read(pSong, pLData, size);
				if (!err) err = Pattern_Decode(pSong, i, &pSong->pPatterns[i], channels, beat, pLData, pLData + size);
				if (err) goto loader_err;

				Loaders_Free(pSong, pLData);
				pLData = NULL;
			}
		}
		else if (Tag == TAG(INST))
		{
			uint32_t range, sample, flags;

			// Set instrument mode
			pSong->Flags |= Song_Flag_Instruments;

			if (pSong->Instruments > 0)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}

			err = FileLoad_ReadByte(pSong, &pSong->Instruments);
			if (err) goto loader_err;

			if (!pSong->Instruments)
			{
				err = Loaders_InvalidSong(pSong, FileOffset, &pSong->Instruments, pSong->Instruments);
				goto loader_err;
			}

			// Read instruments definitions
			for(i = 0, pInst = pSong->pInstruments; i < pSong->Instruments; i++, pInst++)
			{
				if (FileOffset + TagSize < FileLoad_GetPos(pSong) + 38)
				{
					SysLog_FileCorrupted
						( SysLog_High, pSong, FileOffset - 8
						, "Block INST cannot contain %d instruments"
						, pSong->Instruments
						);
					break;
				}
				// read instrument name
				err = FileLoad_ReadString(pSong, &pInst->pName, 30, false);
				if (err) goto loader_err;
				// read instrument flags
				err = FileLoad_ReadByte(pSong, &flags);
				if (err) goto loader_err;
				// read range
				err = FileLoad_ReadByte(pSong, &range);
				if (err) goto loader_err;
				err = Loaders_AllocMapTable(pSong, &pInst->pNotesMap);
				if (err) goto loader_err;
				for (j = 0, k = NoteDelta; j < range; j++)
				{
					// read sample
					err = FileLoad_ReadByte(pSong, &sample);
					if (err) goto loader_err;
					// read length
					err = FileLoad_ReadByte(pSong, &val);
					if (err) goto loader_err;
					for (; val && (k <= Note_Max); val--, k++)
					{
						NoteMap* pn = pInst->pNotesMap + k;
						pn->Volume = 255;
						pn->SampleNr = sample;
						pn->Pitch = k << 8;
					}
				}
				// Envelope
				err = FileLoad_Skip(pSong, 6);
			}
		}
		else if (Tag == TAG(SMPI))
		{
			if (pSong->Samples > 0)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}

			err = FileLoad_ReadByte(pSong, &pSong->Samples);
			if (err) goto loader_err;

			if (!pSong->Samples)
			{
				err = Loaders_InvalidSong(pSong, -1, &pSong->Samples, pSong->Samples);
				goto loader_err;
			}

			// Read sample definitions
			for(i = 0, pSmp = pSong->pSamples; i < pSong->Samples; i++, pSmp++)
			{
				// read name length
				err = FileLoad_ReadByte(pSong, &val);
				if (err) goto loader_err;
				// read sample name
				err = FileLoad_ReadString(pSong, &pSmp->pName, val, false);
				if (err) goto loader_err;
				// read sample size
				err = FileLoad_ReadInt(pSong, &pSmp->Size, 4);
				if (err) goto loader_err;
				// read sample loop start
				err = FileLoad_ReadInt(pSong, &pSmp->LoopStart, 4);
				if (err) goto loader_err;
				// read sample loop size
				err = FileLoad_ReadInt(pSong, &pSmp->LoopEnd, 4);
				if (err) goto loader_err;
				// read sample frequency
				err = FileLoad_ReadInt(pSong, &val, 2);
				if (err) goto loader_err;
				pSmp->Frequency = 8364;
				pSmp->RelTone = Convert_RelTone(pSmp->Frequency, val);
				// read sample volume
				err = FileLoad_ReadByte(pSong, &pSmp->DefaultVolume);
				if (err) goto loader_err;
				if (!pSmp->DefaultVolume) pSmp->DefaultVolume = 256;
				// read flags
				err = FileLoad_ReadByte(pSong, &val);
				if (err) goto loader_err;
				pSmp->Type = 0;
				if (val & 0x01) pSmp->Type |= Smp_Type_Loop;
				if (val & 0x02)
				{
					pSmp->Type |= Smp_Type_16bit;
					pSmp->Size >>= 1;
				}
				// Use as temp
				pSmp->Panning = val;
				// read dummy
				err = FileLoad_Skip(pSong, (pSong->Version >= 800) ? 14 : 6);
				if (err) goto loader_err;
			}
		}
		else if (Tag == TAG(SMPD))
		{
			uint32_t size, NextOffset;

			if (!pSong->Samples)
			{
				err = Loaders_Error(pSong, -8, Unexpected_Block);
				goto loader_err;
			}

			// Read sample data
			for(i = 0, pSmp = pSong->pSamples; i < pSong->Samples; i++, pSmp++)
			{
				// Stored in file?
				if (!(pSmp->Panning & 0x80))
				{
					if (FileOffset + TagSize < FileLoad_GetPos(pSong) + 4)
					{
						SysLog_FileCorrupted
							( SysLog_High, pSong, FileOffset - 8
							, "Block SMPD cannot contain sample %d"
							, i
							);
						break;
					}

					// read sample size
					err = FileLoad_ReadInt(pSong, &size, 4);
					if (err) goto loader_err;
					if (FileOffset + TagSize < FileLoad_GetPos(pSong) + size)
					{
						SysLog_FileCorrupted
							( SysLog_High, pSong, FileOffset - 8
							, "Block SMPD cannot contain sample %d"
							, i
							);
						size = FileOffset + TagSize - FileLoad_GetPos(pSong);
					}
					NextOffset = FileLoad_GetPos(pSong) + size;

					// Packing ?
					if (pSmp->Panning >> 2)
					{
						if ((pSmp->Panning >> 2) != 1)
						{
							SysLog_FileCorrupted
								( SysLog_High, pSong, 0
								, "Unsupported packing %x in sample %d"
								, pSmp->Panning >> 2, i
								);
						}
						err = Loaders_Alloc(pSong, (void**) &pLData, size);
						if (!err) err = FileLoad_Read(pSong, pLData, size);
						if (!err) err = unpack(pSong, pSmp, pLData, pLData + size);
						if (err) goto loader_err;

						Loaders_Free(pSong, pLData);
						pLData = NULL;
					}
					else
					{
						// read data
						if (pSmp->Type & Smp_Type_16bit)
							size >>= 1;

						if (pSmp->Size != size)
						{
							SysLog_FileCorrupted
								( SysLog_High, pSong, -4
								, "Sample %d, expected size %d, got %d instead"
								, i, pSmp->Size, size
								);
							pSmp->Size = size;
						}

						err = FileLoad_ReadSample(pSong, pSmp);
						if (err) goto loader_err;
					}
					FileLoad_SetPos(pSong, NextOffset);
				}
			}
		}
		else if (Tag == TAG(CRAP))
		{
			// Ignore
		}
		else
		{
			SysLog_FileCorrupted(SysLog_Medium, pSong, -8, Unexpected_Block);
		}

		FileLoad_SetPos(pSong, FileOffset + TagSize);
	}

loader_err:
	Loaders_Free(pSong, pLHdr);
	Loaders_Free(pSong, pLData);

	return err;
}
