/*************************************************************************** * __________ __ ___. * Open \______ \ ____ ____ | | _\_ |__ _______ ___ * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ * \/ \/ \/ \/ \/ * $Id$ * * MOD Codec for rockbox * * Written from scratch by Rainer Sinsch * exclusivly for Rockbox in February 2008 * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY * KIND, either express or implied. * ****************************************************************************/ /************** * This version supports large files directly from internal memory management. * There is a drawback however: It may happen that a song is not completely * loaded when the internal rockbox-ringbuffer (approx. 28MB) is filled up * As a workaround make sure you don't have directories with mods larger * than a total of 28MB *************/ #include "debug.h" #include "codeclib.h" #include #include #include #include #include CODEC_HEADER #define CHUNK_SIZE (1024*2) /* This codec supports MOD Files: * */ static int32_t samples[CHUNK_SIZE] IBSS_ATTR; /* The sample buffer */ /* Instrument Data */ struct s_instrument { /* Sample name / description */ /*char description[22];*/ /* Sample length in bytes */ unsigned short length; /* Sample finetuning (-8 - +7) */ signed char finetune; /* Sample volume (0 - 64) */ signed char volume; /* Sample Repeat Position */ unsigned short repeatoffset; /* Sample Repeat Length */ unsigned short repeatlength; /* Offset to sample data */ unsigned int sampledataoffset; }; /* Song Data */ struct s_song { /* Song name / title description */ /*char szTitle[20];*/ /* No. of channels in song */ unsigned char noofchannels; /* No. of instruments used (either 15 or 31) */ unsigned char noofinstruments; /* How many patterns are beeing played? */ unsigned char songlength; /* Where to jump after the song end? */ unsigned char songendjumpposition; /* Pointer to the Pattern Order Table */ unsigned char *patternordertable; /* Pointer to the pattern data */ void *patterndata; /* Pointer to the sample buffer */ signed char *sampledata; /* Instrument data */ struct s_instrument instrument[31]; }; struct s_modchannel { /* Current Volume */ signed char volume; /* Current Offset to period in PeriodTable of notebeeing played (can be temporarily negative) */ short periodtableoffset; /* Current Period beeing played */ short period; /* Current effect */ unsigned char effect; /* Current parameters of effect */ unsigned char effectparameter; /* Current Instrument beeing played */ unsigned char instrument; /* Current Vibrato Speed */ unsigned char vibratospeed; /* Current Vibrato Depth */ unsigned char vibratodepth; /* Current Position for Vibrato in SinTable */ unsigned char vibratosinpos; /* Current Tremolo Speed */ unsigned char tremolospeed; /* Current Tremolo Depth */ unsigned char tremolodepth; /* Current Position for Tremolo in SinTable */ unsigned char tremolosinpos; /* Current Speed of Effect "Slide Note up" */ unsigned char slideupspeed; /* Current Speed of Effect "Slide Note down" */ unsigned char slidedownspeed; /* Current Speed of the "Slide to Note" effect */ unsigned char slidetonotespeed; /* Current Period of the "Slide to Note" effect */ unsigned short slidetonoteperiod; }; struct s_modplayer { /* Ticks per Line */ unsigned char ticksperline; /* Beats per Minute */ unsigned char bpm; /* Position of the Song in the Pattern Table (0-127) */ unsigned char patterntableposition; /* Current Line (may be temporarily < 0) */ signed char currentline; /* Current Tick */ signed char currenttick; /* How many samples are required to calculate for each tick? */ unsigned int samplespertick; /* Information about the channels */ struct s_modchannel modchannel[8]; /* The Amiga Period Table */ unsigned short *periodtable; /* The sinus table [-255,255] */ signed short *sintable; /* Is the glissando effect enabled? */ bool glissandoenabled; /* Is the Amiga Filter enabled? */ bool amigafilterenabled; /* The pattern-line where the loop is carried out (set with e6 command) */ unsigned char loopstartline; /* Number of times to loop */ unsigned char looptimes; }; struct s_channel { /* Panning (0 = left, 16 = right) */ unsigned char panning; /* Sample frequency of the channel */ unsigned short frequency; /* Position of the sample currently played */ unsigned int samplepos; /* Fractual Position of the sample currently player */ unsigned int samplefractpos; /* Loop Sample */ bool loopsample; /* Loop Position Start */ unsigned int loopstart; /* Loop Position End */ unsigned int loopend; /* Is The channel beeing played? */ bool channelactive; /* The Volume (0..64) */ signed char volume; /* The last sampledata beeing played (required for interpolation) */ signed short lastsampledata; }; struct s_mixer { /* The channels */ struct s_channel channel[32]; }; struct s_song modsong IDATA_ATTR; /* The Song */ struct s_modplayer modplayer IDATA_ATTR; /* The Module Player */ struct s_mixer mixer IDATA_ATTR; /* The Amiga Period Table (+1 because we use index 0 for period 0 = no new note) */ static unsigned short s_periodtable[37*8+1] IDATA_ATTR = { 0, 907, 900, 893, 887, 881, 874, 868, 862, 856, 849, 843, 837, 831, 825, 819, 813, 808, 802, 796, 790, 785, 779, 773, 768, 762, 757, 751, 746, 740, 735, 730, 725, 719, 714, 709, 704, 699, 694, 689, 684, 679, 674, 669, 664, 660, 655, 650, 645, 641, 636, 632, 627, 623, 618, 614, 609, 605, 600, 596, 592, 588, 583, 579, 575, 571, 567, 563, 559, 555, 551, 547, 543, 539, 535, 531, 527, 523, 520, 516, 512, 509, 505, 501, 498, 494, 490, 487, 483, 480, 477, 473, 470, 466, 463, 460, 456, 453, 450, 446, 443, 440, 437, 434, 431, 428, 424, 421, 418, 415, 412, 409, 406, 404, 401, 398, 395, 392, 389, 386, 384, 381, 378, 375, 373, 370, 367, 365, 362, 359, 357, 354, 352, 349, 347, 344, 342, 339, 337, 334, 332, 330, 327, 325, 322, 320, 318, 316, 313, 311, 309, 307, 304, 302, 300, 298, 296, 294, 291, 289, 287, 285, 283, 281, 279, 277, 275, 273, 271, 269, 267, 265, 263, 261, 260, 258, 256, 254, 252, 250, 249, 247, 245, 243, 241, 240, 238, 236, 235, 233, 231, 230, 228, 226, 225, 223, 221, 220, 218, 217, 215, 214, 212, 210, 209, 207, 206, 204, 203, 202, 200, 199, 197, 196, 194, 193, 192, 190, 189, 187, 186, 185, 183, 182, 181, 179, 178, 177, 176, 174, 173, 172, 171, 169, 168, 167, 166, 165, 163, 162, 161, 160, 159, 158, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 120, 119, 118, 117, 116, 115, 115, 114, 113, 112, 111, 110, 110, 109, 108, 107}; /* The sin table */ static signed short s_sintable[0x40] IDATA_ATTR = { 0, 25, 49, 74, 97, 120, 141, 162, 180, 197, 212, 225, 235, 244, 250, 254, 255, 254, 250, 244, 235, 225, 212, 197, 180, 161, 141, 120, 97, 73, 49, 24, 0, -25, -50, -74, -98, -120, -142, -162, -180, -197, -212, -225, -236, -244, -250, -254, -255, -254, -250, -244, -235, -224, -211, -197, -180, -161, -141, -119, -97, -73, -49, -24}; const unsigned short mixingrate = 44100; static void mixer_playsample(int channel, int instrument) ICODE_ATTR; void mixer_playsample(int channel, int instrument) { struct s_channel *p_channel = &mixer.channel[channel]; struct s_instrument *p_instrument = &modsong.instrument[instrument]; p_channel->channelactive = true; p_channel->samplepos = p_instrument->sampledataoffset; p_channel->samplefractpos = 0; p_channel->loopsample = (p_instrument->repeatlength > 2); if (p_channel->loopsample) { p_channel->loopstart = p_instrument->repeatoffset + p_instrument->sampledataoffset; p_channel->loopend = p_channel->loopstart + p_instrument->repeatlength; } else p_channel->loopend = p_instrument->length + p_instrument->sampledataoffset; /* Remember the instrument */ modplayer.modchannel[channel].instrument = instrument; } static inline void mixer_stopsample(int channel) { mixer.channel[channel].channelactive = false; } static inline void mixer_continuesample(int channel) { mixer.channel[channel].channelactive = true; } static inline void mixer_setvolume(int channel, int volume) { mixer.channel[channel].volume = volume; } static inline void mixer_setpanning(int channel, int panning) { mixer.channel[channel].panning = panning; } static inline void mixer_setamigaperiod(int channel, int amigaperiod) { /* Just to make sure we don't devide by zero * amigaperiod shouldn't 0 anyway - if it is the case * then something terribly went wrong */ if (amigaperiod == 0) return; mixer.channel[channel].frequency = 3579546 / amigaperiod; } /* Initialize the MOD Player with default values and precalc tables */ static void initmodplayer(void) ICODE_ATTR; void initmodplayer(void) { unsigned int c; #if 0 /* As the calculation of periodtable and sintable uses float and double * rockbox uses two predefined tables. This reduces the codesize by * several KB. */ unsigned int i; /* Calculate Amiga Period Values * Start with Period 907 (= C-1 with Finetune -8) and work upwards */ double f = 907.0f; /* Index 0 stands for no note (and therefore no period) */ modplayer.periodtable[0] = 0; for (i=1;i<297;i++) { modplayer.periodtable[i] = (unsigned short) f; f /= 1.0072464122237039; /* = pow(2.0f, 1.0f/(12.0f*8.0f)); */ } /* * This is a more accurate but also time more consuming approach * to calculate the amiga period table * Commented out for speed purposes const int finetuning = 8; const int octaves = 3; for (int halftone=0;halftone<=finetuning*octaves*12+7;halftone++) { float e = pow(2.0f, halftone/(12.0f*8.0f)); float f = 906.55f/e; modplayer.periodtable[halfetone+1] = (int)(f+0.5f); } */ /* Calculate Protracker Vibrato sine table * The routine makes use of the Harmonical Oscillator Approach * for calculating sine tables * (see http://membres.lycos.fr/amycoders/tutorials/sintables.html) * The routine presented here calculates a complete sine wave * with 64 values in range [-255,255] */ float a, b, d, dd; d = 0.09817475f; /* = 2*PI/64 */ dd = d*d; a = 0; b = d; for (i=0;i<0x40;i++) { modplayer.sintable[i] = (int)(255*a); a = a+b; b = b-dd*a; } #else /* Point to the predefined tables */ modplayer.periodtable = s_periodtable; modplayer.sintable = s_sintable; #endif /* Set Default Player Values */ modplayer.currentline = 0; modplayer.currenttick = 0; modplayer.patterntableposition = 0; modplayer.bpm = 125; modplayer.ticksperline = 6; modplayer.glissandoenabled = false; /* Disable glissando */ modplayer.amigafilterenabled = false; /* Disable the Amiga Filter */ /* Default Panning Values */ int panningvalues[8] = {4,12,12,4,4,12,12,4}; for (c=0;c<8;c++) { /* Set Default Panning */ mixer_setpanning(c, panningvalues[c]); /* Reset channels in the MOD Player */ memset(&modplayer.modchannel[c], 0, sizeof(struct s_modchannel)); /* Don't play anything */ mixer.channel[c].channelactive = false; } } /* Load the MOD File from memory */ static bool loadmod(void *modfile) ICODE_ATTR; bool loadmod(void *modfile) { int i; unsigned char *periodsconverted; /* We don't support PowerPacker 2.0 Files */ if (memcmp((char*) modfile, "PP20", 4) == 0) return false; /* Get the File Format Tag */ char *fileformattag = (char*)modfile + 1080; /* Find out how many channels and instruments are used */ if (memcmp(fileformattag, "2CHN", 4) == 0) {modsong.noofchannels = 2; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "M.K.", 4) == 0) {modsong.noofchannels = 4; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "M!K!", 4) == 0) {modsong.noofchannels = 4; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "4CHN", 4) == 0) {modsong.noofchannels = 4; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "FLT4", 4) == 0) {modsong.noofchannels = 4; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "6CHN", 4) == 0) {modsong.noofchannels = 6; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "8CHN", 4) == 0) {modsong.noofchannels = 8; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "OKTA", 4) == 0) {modsong.noofchannels = 8; modsong.noofinstruments = 31;} else if (memcmp(fileformattag, "CD81", 4) == 0) {modsong.noofchannels = 8; modsong.noofinstruments = 31;} else { /* The file has no format tag, so most likely soundtracker */ modsong.noofchannels = 4; modsong.noofinstruments = 15; } /* Get the Song title * Skipped here * strncpy(modsong.szTitle, (char*)pMODFile, 20); */ /* Get the Instrument information */ for (i=0;idescription, (char*)p, 22); */ p += 22; instrument->length = (((p[0])<<8) + p[1]) << 1; p+=2; instrument->finetune = *p++ & 0x0f; /* Treat finetuning as signed nibble */ if (instrument->finetune > 7) instrument->finetune -= 16; instrument->volume = *p++; instrument->repeatoffset = (((p[0])<<8) + p[1]) << 1; p+= 2; instrument->repeatlength = (((p[0])<<8) + p[1]) << 1; } /* Get the pattern information */ unsigned char *p = (unsigned char *)modfile + 20 + modsong.noofinstruments*30; modsong.songlength = *p++; modsong.songendjumpposition = *p++; modsong.patternordertable = p; /* Find out how many patterns are used within this song */ int maxpatterns = 0; for (i=0;i<128;i++) if (modsong.patternordertable[i] > maxpatterns) maxpatterns = modsong.patternordertable[i]; maxpatterns++; /* use 'restartposition' (historically set to 127) which is not used here as a marker that periods have already been converted */ periodsconverted = (char*)modfile + 20 + modsong.noofinstruments*30 + 1; /* Get the pattern data; ST doesn't have fileformattag, so 4 bytes less */ modsong.patterndata = periodsconverted + (modsong.noofinstruments==15 ? 129 : 133); /* Convert the period values in the mod file to offsets * in our periodtable (but only, if we haven't done this yet) */ p = (unsigned char *) modsong.patterndata; if (*periodsconverted != 0xfe) { int note, note2, channel; for (note=0;note> 8) | (p[0] & 0xf0); p[1] = periodoffset & 0xff; p += 4; } /* Remember that we already converted the periods, * in case the file gets reloaded by rewinding * with 0xfe (arbitary magic value > 127) */ *periodsconverted = 0xfe; } /* Get the samples * Calculation: The Samples come after the pattern data * We know that there are nMaxPatterns and each pattern requires * 4 bytes per note and per channel. * And of course there are always lines in each channel */ modsong.sampledata = (signed char*) modsong.patterndata + maxpatterns*4*modsong.noofchannels*64; int sampledataoffset = 0; for (i=0;i> 7 is used in the original protracker source code */ mixer_setamigaperiod(channel, p_modchannel->period+ ((p_modchannel->vibratodepth * modplayer.sintable[p_modchannel->vibratosinpos])>>7)); /* Foward in Sine Table */ p_modchannel->vibratosinpos += p_modchannel->vibratospeed; p_modchannel->vibratosinpos &= 0x3f; } /* Apply tremolo to channel * (same as vibrato, but only apply on volume instead of pitch) */ static void tremolo(int channel) ICODE_ATTR; void tremolo(int channel) { struct s_modchannel *p_modchannel = &modplayer.modchannel[channel]; /* Apply Tremolo * >> 6 is used in the original protracker source code */ int volume = (p_modchannel->volume * modplayer.sintable[p_modchannel->tremolosinpos])>>6; if (volume > 64) volume = 64; else if (volume < 0) volume = 0; mixer_setvolume(channel, volume); /* Foward in Sine Table */ p_modchannel->tremolosinpos += p_modchannel->tremolosinpos; p_modchannel->tremolosinpos &= 0x3f; } /* Apply Slide to Note effect to channel */ static void slidetonote(int channel) ICODE_ATTR; void slidetonote(int channel) { struct s_modchannel *p_modchannel = &modplayer.modchannel[channel]; /* If there hasn't been any slide-to note set up, then return */ if (p_modchannel->slidetonoteperiod == 0) return; /* Slide note up */ if (p_modchannel->slidetonoteperiod > p_modchannel->period) { p_modchannel->period += p_modchannel->slidetonotespeed; if (p_modchannel->period > p_modchannel->slidetonoteperiod) p_modchannel->period = p_modchannel->slidetonoteperiod; } /* Slide note down */ else if (p_modchannel->slidetonoteperiod < p_modchannel->period) { p_modchannel->period -= p_modchannel->slidetonotespeed; if (p_modchannel->period < p_modchannel->slidetonoteperiod) p_modchannel->period = p_modchannel->slidetonoteperiod; } mixer_setamigaperiod(channel, p_modchannel->period); } /* Apply Slide to Note effect on channel, * but this time with glissando enabled */ static void slidetonoteglissando(int channel) ICODE_ATTR; void slidetonoteglissando(int channel) { struct s_modchannel *p_modchannel = &modplayer.modchannel[channel]; /* Slide note up */ if (p_modchannel->slidetonoteperiod > p_modchannel->period) { p_modchannel->period = modplayer.periodtable[p_modchannel->periodtableoffset+=8]; if (p_modchannel->period > p_modchannel->slidetonoteperiod) p_modchannel->period = p_modchannel->slidetonoteperiod; } /* Slide note down */ else { p_modchannel->period = modplayer.periodtable[p_modchannel->periodtableoffset-=8]; if (p_modchannel->period < p_modchannel->slidetonoteperiod) p_modchannel->period = p_modchannel->slidetonoteperiod; } mixer_setamigaperiod(channel, p_modchannel->period); } /* Apply Volume Slide */ static void volumeslide(int channel, int effectx, int effecty) ICODE_ATTR; void volumeslide(int channel, int effectx, int effecty) { struct s_modchannel *p_modchannel = &modplayer.modchannel[channel]; /* If both X and Y Parameters are non-zero, then the y value is ignored */ if (effectx > 0) { p_modchannel->volume += effectx; if (p_modchannel->volume > 64) p_modchannel->volume = 64; } else { p_modchannel->volume -= effecty; if (p_modchannel->volume < 0) p_modchannel->volume = 0; } mixer_setvolume(channel, p_modchannel->volume); } /* Play the current line (at tick 0) */ static void playline(int pattern, int line) ICODE_ATTR; void playline(int pattern, int line) { int c; /* Get pointer to the current pattern */ unsigned char *p_line = (unsigned char*)modsong.patterndata; p_line += pattern*64*4*modsong.noofchannels; p_line += line*4*modsong.noofchannels; /* Only allow one Patternbreak Commando per Line */ bool patternbreakdone = false; for (c=0;c> 4); short periodtableoffset = ((p_note[0] & 0x0f) << 8) | p_note[1]; p_modchannel->effect = p_note[2] & 0x0f; p_modchannel->effectparameter = p_note[3]; /* Remember Instrument and set Volume if new Instrument triggered */ if (samplenumber > 0) { /* And trigger new sample, if new instrument was set */ if (samplenumber-1 != p_modchannel->instrument) { /* Advance the new sample to the same offset * the old sample was beeing played */ int oldsampleoffset = mixer.channel[c].samplepos - modsong.instrument[ p_modchannel->instrument].sampledataoffset; mixer_playsample(c, samplenumber-1); mixer.channel[c].samplepos += oldsampleoffset; } /* Remember last played instrument on channel */ p_modchannel->instrument = samplenumber-1; /* Set Volume to standard instrument volume, * if not overwritten by volume effect */ if (p_modchannel->effect != 0x0c) { p_modchannel->volume = modsong.instrument[ p_modchannel->instrument].volume; mixer_setvolume(c, p_modchannel->volume); } } /* Trigger new sample if note available */ if (periodtableoffset > 0) { /* Restart instrument only when new sample triggered */ if (samplenumber != 0) mixer_playsample(c, (samplenumber > 0) ? samplenumber-1 : p_modchannel->instrument); /* Set the new amiga period * (but only, if there is no slide to note effect) */ if ((p_modchannel->effect != 0x3) && (p_modchannel->effect != 0x5)) { /* Apply finetuning to sample */ p_modchannel->periodtableoffset = periodtableoffset + modsong.instrument[p_modchannel->instrument].finetune; p_modchannel->period = modplayer.periodtable[ p_modchannel->periodtableoffset]; mixer_setamigaperiod(c, p_modchannel->period); /* When a new note is played without slide to note setup, * then disable slide to note */ modplayer.modchannel[c].slidetonoteperiod = p_modchannel->period; } } int effectx = p_modchannel->effectparameter>>4; int effecty = p_modchannel->effectparameter&0x0f; switch (p_modchannel->effect) { /* Effect 0: Arpeggio */ case 0x00: /* Set the base period on tick 0 */ if (p_modchannel->effectparameter > 0) mixer_setamigaperiod(c, modplayer.periodtable[ p_modchannel->periodtableoffset]); break; /* Slide up (Portamento up) */ case 0x01: if (p_modchannel->effectparameter > 0) p_modchannel->slideupspeed = p_modchannel->effectparameter; break; /* Slide down (Portamento down) */ case 0x02: if (p_modchannel->effectparameter > 0) p_modchannel->slidedownspeed = p_modchannel->effectparameter; break; /* Slide to Note */ case 0x03: if (p_modchannel->effectparameter > 0) p_modchannel->slidetonotespeed = p_modchannel->effectparameter; /* Get the slide to note directly from the pattern buffer */ if (periodtableoffset > 0) p_modchannel->slidetonoteperiod = modplayer.periodtable[periodtableoffset + modsong.instrument[ p_modchannel->instrument].finetune]; /* If glissando is enabled apply the effect directly here */ if (modplayer.glissandoenabled) slidetonoteglissando(c); break; /* Set Vibrato */ case 0x04: if (effectx > 0) p_modchannel->vibratospeed = effectx; if (effecty > 0) p_modchannel->vibratodepth = effecty; break; /* Effect 0x06: Slide to note */ case 0x05: /* Get the slide to note directly from the pattern buffer */ if (periodtableoffset > 0) p_modchannel->slidetonoteperiod = modplayer.periodtable[periodtableoffset + modsong.instrument[ p_modchannel->instrument].finetune]; break; /* Effect 0x06 is "Continue Effects" */ /* It is not processed on tick 0 */ case 0x06: break; /* Set Tremolo */ case 0x07: if (effectx > 0) p_modchannel->tremolodepth = effectx; if (effecty > 0) p_modchannel->tremolospeed = effecty; break; /* Set fine panning */ case 0x08: /* Internal panning goes from 0..15 * Scale the fine panning value to that range */ mixer.channel[c].panning = p_modchannel->effectparameter>>4; break; /* Set Sample Offset */ case 0x09: { struct s_instrument *p_instrument = &modsong.instrument[p_modchannel->instrument]; int sampleoffset = p_instrument->sampledataoffset; if (sampleoffset > p_instrument->length) sampleoffset = p_instrument->length; /* Forward the new offset to the mixer */ mixer.channel[c].samplepos = p_instrument->sampledataoffset + (p_modchannel->effectparameter<<8); mixer.channel[c].samplefractpos = 0; break; } /* Effect 0x0a (Volume slide) is not processed on tick 0 */ /* Position Jump */ case 0x0b: modplayer.currentline = -1; modplayer.patterntableposition = (effectx<<4)+effecty; break; /* Set Volume */ case 0x0c: p_modchannel->volume = p_modchannel->effectparameter; mixer_setvolume(c, p_modchannel->volume); break; /* Pattern break */ case 0x0d: modplayer.currentline = effectx*10 + effecty - 1; if (!patternbreakdone) { patternbreakdone = true; modplayer.patterntableposition++; } break; /* Extended Effects */ case 0x0e: switch (effectx) { /* Set Filter */ case 0x0: modplayer.amigafilterenabled = (effecty == 0); break; /* Fineslide up */ case 0x1: mixer_setamigaperiod(c, p_modchannel->period -= effecty); if (p_modchannel->period < modplayer.periodtable[37*8]) p_modchannel->period = 100; /* Find out the new offset in the period table */ if (p_modchannel->periodtableoffset < 36*8) while (modplayer.periodtable[ p_modchannel->periodtableoffset+8] >= p_modchannel->period) p_modchannel->periodtableoffset+=8; break; /* Fineslide down */ case 0x2: mixer_setamigaperiod(c, p_modchannel->period += effecty); if (p_modchannel->periodtableoffset > 8) while (modplayer.periodtable[ p_modchannel->periodtableoffset-8] <= p_modchannel->period) p_modchannel->periodtableoffset-=8; break; /* Set glissando on/off */ case 0x3: modplayer.glissandoenabled = (effecty > 0); break; /* Set Vibrato waveform */ case 0x4: /* Currently not implemented */ break; /* Set Finetune value */ case 0x5: /* Treat as signed nibble */ if (effecty > 7) effecty -= 16; p_modchannel->periodtableoffset += effecty - modsong.instrument[ p_modchannel->instrument].finetune; p_modchannel->period = modplayer.periodtable[ p_modchannel->periodtableoffset]; modsong.instrument[ p_modchannel->instrument].finetune = effecty; break; /* Pattern loop */ case 0x6: if (effecty == 0) modplayer.loopstartline = line-1; else { if (modplayer.looptimes == 0) { modplayer.currentline = modplayer.loopstartline; modplayer.looptimes = effecty; } else modplayer.looptimes--; if (modplayer.looptimes > 0) modplayer.currentline = modplayer.loopstartline; } break; /* Set Tremolo waveform */ case 0x7: /* Not yet implemented */ break; /* Enhanced Effect 8 is not used */ case 0x8: break; /* Retrigger sample */ case 0x9: /* Only processed on subsequent ticks */ break; /* Fine volume slide up */ case 0xa: p_modchannel->volume += effecty; if (p_modchannel->volume > 64) p_modchannel->volume = 64; mixer_setvolume(c, p_modchannel->volume); break; /* Fine volume slide down */ case 0xb: p_modchannel->volume -= effecty; if (p_modchannel->volume < 0) p_modchannel->volume = 0; mixer_setvolume(c, p_modchannel->volume); break; /* Cut sample */ case 0xc: /* Continue sample */ mixer_continuesample(c); break; /* Note delay (Usage: $ED + ticks to delay note.) */ case 0xd: /* We stop the sample here on tick 0 * and restart it later in the effect */ if (effecty > 0) mixer.channel[c].channelactive = false; break; } break; /* Set Speed */ case 0x0f: if (p_modchannel->effectparameter < 32) modplayer.ticksperline = p_modchannel->effectparameter; else modplayer.bpm = p_modchannel->effectparameter; break; } } } /* Play the current effect of the note (ticks 1..speed) */ static void playeffect(int currenttick) ICODE_ATTR; void playeffect(int currenttick) { int c; for (c=0;cperiod == 0) continue; unsigned char effectx = p_modchannel->effectparameter>>4; unsigned char effecty = p_modchannel->effectparameter&0x0f; switch (p_modchannel->effect) { /* Effect 0: Arpeggio */ case 0x00: if (p_modchannel->effectparameter > 0) { unsigned short newperiodtableoffset; switch (currenttick % 3) { case 0: mixer_setamigaperiod(c, modplayer.periodtable[ p_modchannel->periodtableoffset]); break; case 1: newperiodtableoffset = p_modchannel->periodtableoffset+(effectx<<3); if (newperiodtableoffset < 37*8) mixer_setamigaperiod(c, modplayer.periodtable[ newperiodtableoffset]); break; case 2: newperiodtableoffset = p_modchannel->periodtableoffset+(effecty<<3); if (newperiodtableoffset < 37*8) mixer_setamigaperiod(c, modplayer.periodtable[ newperiodtableoffset]); break; } } break; /* Effect 1: Slide Up */ case 0x01: mixer_setamigaperiod(c, p_modchannel->period -= p_modchannel->slideupspeed); /* Find out the new offset in the period table */ if (p_modchannel->periodtableoffset <= 37*8) while (modplayer.periodtable[ p_modchannel->periodtableoffset] > p_modchannel->period) { p_modchannel->periodtableoffset++; /* Make sure we don't go out of range */ if (p_modchannel->periodtableoffset > 37*8) { p_modchannel->periodtableoffset = 37*8; break; } } break; /* Effect 2: Slide Down */ case 0x02: mixer_setamigaperiod(c, p_modchannel->period += p_modchannel->slidedownspeed); /* Find out the new offset in the period table */ if (p_modchannel->periodtableoffset > 8) while (modplayer.periodtable[ p_modchannel->periodtableoffset] < p_modchannel->period) { p_modchannel->periodtableoffset--; /* Make sure we don't go out of range */ if (p_modchannel->periodtableoffset < 1) { p_modchannel->periodtableoffset = 1; break; } } break; /* Effect 3: Slide to Note */ case 0x03: /* Apply smooth sliding, if no glissando is enabled */ if (modplayer.glissandoenabled == 0) slidetonote(c); break; /* Effect 4: Vibrato */ case 0x04: vibrate(c); break; /* Effect 5: Continue effect 3:'Slide to note', * but also do Volume slide */ case 0x05: slidetonote(c); volumeslide(c, effectx, effecty); break; /* Effect 6: Continue effect 4:'Vibrato', * but also do Volume slide */ case 0x06: vibrate(c); volumeslide(c, effectx, effecty); break; /* Effect 7: Tremolo */ case 0x07: tremolo(c); break; /* Effect 8 (Set fine panning) is only processed at tick 0 */ /* Effect 9 (Set sample offset) is only processed at tick 0 */ /* Effect A: Volume slide */ case 0x0a: volumeslide(c, effectx, effecty); break; /* Effect B (Position jump) is only processed at tick 0 */ /* Effect C (Set Volume) is only processed at tick 0 */ /* Effect D (Pattern Preak) is only processed at tick 0 */ /* Effect E (Enhanced Effect) */ case 0x0e: switch (effectx) { /* Retrigger sample ($E9 + Tick to Retrig note at) */ case 0x9: /* Don't device by zero */ if (effecty == 0) effecty = 1; /* Apply retrig */ if (currenttick % effecty == 0) mixer_playsample(c, p_modchannel->instrument); break; /* Cut note (Usage: $EC + Tick to Cut note at) */ case 0xc: if (currenttick == effecty) mixer_stopsample(c); break; /* Delay note (Usage: $ED + ticks to delay note) */ case 0xd: /* If this is the correct tick, * we start playing the sample now */ if (currenttick == effecty) mixer.channel[c].channelactive = true; break; } break; /* Effect F (Set Speed) is only processed at tick 0 */ } } } static inline int clip(int i) { if (i > 32767) return(32767); else if (i < -32768) return(-32768); else return(i); } static void synthrender(int32_t *renderbuffer, int samplecount) ICODE_ATTR; void synthrender(int32_t *renderbuffer, int samplecount) { /* 125bpm equals to 50Hz (= 0.02s) * => one tick = mixingrate/50, * samples passing in one tick: * mixingrate/(bpm/2.5) = 2.5*mixingrate/bpm */ int32_t *p_left = renderbuffer; /* int in rockbox */ int32_t *p_right = p_left+1; signed short s; int qf_distance, qf_distance2; int i; int c, left, right; for (i=0;i= modplayer.ticksperline) { modplayer.currentline++; modplayer.currenttick = 0; if (modplayer.currentline == 64) { modplayer.patterntableposition++; if (modplayer.patterntableposition >= modsong.songlength) /* This is for Noise Tracker * modplayer.patterntableposition = * modsong.songendjumpposition; * More compatible approach is restart from 0 */ modplayer.patterntableposition=0; modplayer.currentline = 0; } } modplayer.samplespertick = (20*mixingrate/modplayer.bpm)>>3; } /* Mix buffers from here * Walk through all channels */ left=0, right=0; /* If song has not stopped playing */ if (modplayer.patterntableposition < 127) /* Loop through all channels */ for (c=0;c= mixer.channel[c].loopend) { if (mixer.channel[c].loopsample) mixer.channel[c].samplepos -= (mixer.channel[c].loopend- mixer.channel[c].loopstart); else mixer.channel[c].channelactive = false; } /* If the sample has stopped playing don't mix it */ if (!mixer.channel[c].channelactive) continue; /* Get the sample */ s = (signed short)(modsong.sampledata[ mixer.channel[c].samplepos]*mixer.channel[c].volume); /* Interpolate if the sample-frequency is lower * than the mixing rate * If you don't want interpolation simply skip this part */ if (mixer.channel[c].frequency < mixingrate) { /* Low precision linear interpolation * (fast integer based) */ qf_distance = mixer.channel[c].samplefractpos<<16 / mixingrate; qf_distance2 = (1<<16)-qf_distance; s = (qf_distance*s + qf_distance2* mixer.channel[c].lastsampledata)>>16; } /* Save the last played sample for interpolation purposes */ mixer.channel[c].lastsampledata = s; /* Pan the sample */ left += s*(16-mixer.channel[c].panning)>>3; right += s*mixer.channel[c].panning>>3; /* Advance sample */ mixer.channel[c].samplefractpos += mixer.channel[c].frequency; while (mixer.channel[c].samplefractpos > mixingrate) { mixer.channel[c].samplefractpos -= mixingrate; mixer.channel[c].samplepos++; } } /* If we have more than 4 channels * we have to make sure that we apply clipping */ if (modsong.noofchannels > 4) { *p_left = clip(left)<<13; *p_right = clip(right)<<13; } else { *p_left = left<<13; *p_right = right<<13; } p_left+=2; p_right+=2; } } /* this is the codec entry point */ enum codec_status codec_main(enum codec_entry_call_reason reason) { if (reason == CODEC_LOAD) { /* Make use of 44.1khz */ ci->configure(DSP_SET_FREQUENCY, 44100); /* Sample depth is 28 bit host endian */ ci->configure(DSP_SET_SAMPLE_DEPTH, 28); /* Stereo output */ ci->configure(DSP_SET_STEREO_MODE, STEREO_INTERLEAVED); } return CODEC_OK; } /* this is called for each file to process */ enum codec_status codec_run(void) { size_t n; unsigned char *modfile; int old_patterntableposition; int bytesdone; intptr_t param; if (codec_init()) { return CODEC_ERROR; } codec_set_replaygain(ci->id3); /* Load MOD file */ ci->seek_buffer(0); modfile = ci->request_buffer(&n, ci->filesize); if (!modfile || n < (size_t)ci->filesize) { return CODEC_ERROR; } initmodplayer(); loadmod(modfile); /* The main decoder loop */ ci->set_elapsed(0); bytesdone = 0; old_patterntableposition = 0; while (1) { enum codec_command_action action = ci->get_command(¶m); if (action == CODEC_ACTION_HALT) break; if (action == CODEC_ACTION_SEEK_TIME) { /* New time is ready in param */ modplayer.patterntableposition = param/1000; modplayer.currentline = 0; ci->seek_complete(); } if(old_patterntableposition != modplayer.patterntableposition) { ci->set_elapsed(modplayer.patterntableposition*1000); old_patterntableposition=modplayer.patterntableposition; } synthrender(samples, CHUNK_SIZE/2); bytesdone += CHUNK_SIZE; ci->pcmbuf_insert(samples, NULL, CHUNK_SIZE/2); } return CODEC_OK; } a> 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 
/*
 * 'same game' -- try to remove all the coloured squares by
 *                selecting regions of contiguous colours.
 */

/*
 * TODO on grid generation:
 * 
 *  - Generation speed could still be improved.
 *     * 15x10c3 is the only really difficult one of the existing
 *       presets. The others are all either small enough, or have
 *       the great flexibility given by four colours, that they
 *       don't take long at all.
 *     * I still suspect many problems arise from separate
 * 	 subareas. I wonder if we can also somehow prioritise left-
 * 	 or rightmost insertions so as to avoid area splitting at
 * 	 all where feasible? It's not easy, though, because the
 * 	 current shuffle-then-try-all-options approach to move
 * 	 choice doesn't leave room for `soft' probabilistic
 * 	 prioritisation: we either try all class A moves before any
 * 	 class B ones, or we don't.
 *
 *  - The current generation algorithm inserts exactly two squares
 *    at a time, with a single exception at the beginning of
 *    generation for grids of odd overall size. An obvious
 *    extension would be to permit larger inverse moves during
 *    generation.
 *     * this might reduce the number of failed generations by
 *       making the insertion algorithm more flexible
 *     * on the other hand, it would be significantly more complex
 *     * if I do this I'll need to take out the odd-subarea
 *       avoidance
 *     * a nice feature of the current algorithm is that the
 *       computer's `intended' solution always receives the minimum
 *       possible score, so that pretty much the player's entire
 *       score represents how much better they did than the
 *       computer.
 *
 *  - Is it possible we can _temporarily_ tolerate neighbouring
 *    squares of the same colour, until we've finished setting up
 *    our inverse move?
 *     * or perhaps even not choose the colour of our inserted
 *       region until we have finished placing it, and _then_ look
 *       at what colours border on it?
 *     * I don't think this is currently meaningful unless we're
 *       placing more than a domino at a time.
 *
 *  - possibly write out a full solution so that Solve can somehow
 *    show it step by step?
 *     * aux_info would have to encode the click points
 *     * solve_game() would have to encode not only those click
 * 	 points but also give a move string which reconstructed the
 * 	 initial state
 *     * the game_state would include a pointer to a solution move
 * 	 list, plus an index into that list
 *     * game_changed_state would auto-select the next move if
 * 	 handed a new state which had a solution move list active
 *     * execute_move, if passed such a state as input, would check
 * 	 to see whether the move being made was the same as the one
 * 	 stated by the solution, and if so would advance the move
 * 	 index. Failing that it would return a game_state without a
 * 	 solution move list active at all.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>

#include "puzzles.h"

#define TILE_INNER (ds->tileinner)
#define TILE_GAP (ds->tilegap)
#define TILE_SIZE (TILE_INNER + TILE_GAP)
#define PREFERRED_TILE_SIZE 32
#define BORDER (TILE_SIZE / 2)
#define HIGHLIGHT_WIDTH 2

#define FLASH_FRAME 0.13F

#define COORD(x)  ( (x) * TILE_SIZE + BORDER )
#define FROMCOORD(x)  ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )

#define X(state, i) ( (i) % (state)->params.w )
#define Y(state, i) ( (i) / (state)->params.w )
#define C(state, x, y) ( (y) * (state)->w + (x) )

enum {
    COL_BACKGROUND,
    COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9,
    COL_IMPOSSIBLE, COL_SEL, COL_HIGHLIGHT, COL_LOWLIGHT,
    NCOLOURS
};

/* scoresub is 1 or 2 (for (n-1)^2 or (n-2)^2) */
struct game_params {
    int w, h, ncols, scoresub;
    int soluble;		       /* choose generation algorithm */
};

/* These flags must be unique across all uses; in the game_state,
 * the game_ui, and the drawstate (as they all get combined in the
 * drawstate). */
#define TILE_COLMASK    0x00ff
#define TILE_SELECTED   0x0100 /* used in ui and drawstate */
#define TILE_JOINRIGHT  0x0200 /* used in drawstate */
#define TILE_JOINDOWN   0x0400 /* used in drawstate */
#define TILE_JOINDIAG   0x0800 /* used in drawstate */
#define TILE_HASSEL     0x1000 /* used in drawstate */
#define TILE_IMPOSSIBLE 0x2000 /* used in drawstate */

#define TILE(gs,x,y) ((gs)->tiles[(gs)->params.w*(y)+(x)])
#define COL(gs,x,y) (TILE(gs,x,y) & TILE_COLMASK)
#define ISSEL(gs,x,y) (TILE(gs,x,y) & TILE_SELECTED)

#define SWAPTILE(gs,x1,y1,x2,y2) do {   \
    int t = TILE(gs,x1,y1);               \
    TILE(gs,x1,y1) = TILE(gs,x2,y2);      \
    TILE(gs,x2,y2) = t;                   \
} while (0)

static int npoints(game_params *params, int nsel)
{
    int sdiff = nsel - params->scoresub;
    return (sdiff > 0) ? sdiff * sdiff : 0;
}

struct game_state {
    struct game_params params;
    int n;
    int *tiles; /* colour only */
    int score;
    int complete, impossible;
};

static game_params *default_params(void)
{
    game_params *ret = snew(game_params);
    ret->w = 5;
    ret->h = 5;
    ret->ncols = 3;
    ret->scoresub = 2;
    ret->soluble = TRUE;
    return ret;
}

static const struct game_params samegame_presets[] = {
    { 5, 5, 3, 2, TRUE },
    { 10, 5, 3, 2, TRUE },
#ifdef SLOW_SYSTEM
    { 10, 10, 3, 2, TRUE },
#else
    { 15, 10, 3, 2, TRUE },
#endif
    { 15, 10, 4, 2, TRUE },
    { 20, 15, 4, 2, TRUE }
};

static int game_fetch_preset(int i, char **name, game_params **params)
{
    game_params *ret;
    char str[80];

    if (i < 0 || i >= lenof(samegame_presets))
	return FALSE;

    ret = snew(game_params);
    *ret = samegame_presets[i];

    sprintf(str, "%dx%d, %d colours", ret->w, ret->h, ret->ncols);

    *name = dupstr(str);
    *params = ret;
    return TRUE;
}

static void free_params(game_params *params)
{
    sfree(params);
}

static game_params *dup_params(game_params *params)
{
    game_params *ret = snew(game_params);
    *ret = *params;		       /* structure copy */
    return ret;
}

static void decode_params(game_params *params, char const *string)
{
    char const *p = string;

    params->w = atoi(p);
    while (*p && isdigit((unsigned char)*p)) p++;
    if (*p == 'x') {
	p++;
	params->h = atoi(p);
	while (*p && isdigit((unsigned char)*p)) p++;
    } else {
	params->h = params->w;
    }
    if (*p == 'c') {
	p++;
	params->ncols = atoi(p);
	while (*p && isdigit((unsigned char)*p)) p++;
    } else {
	params->ncols = 3;
    }
    if (*p == 's') {
	p++;
	params->scoresub = atoi(p);
	while (*p && isdigit((unsigned char)*p)) p++;
    } else {
	params->scoresub = 2;
    }
    if (*p == 'r') {
	p++;
	params->soluble = FALSE;
    }
}

static char *encode_params(game_params *params, int full)
{
    char ret[80];

    sprintf(ret, "%dx%dc%ds%d%s",
	    params->w, params->h, params->ncols, params->scoresub,
	    full && !params->soluble ? "r" : "");
    return dupstr(ret);
}

static config_item *game_configure(game_params *params)
{
    config_item *ret;
    char buf[80];

    ret = snewn(6, config_item);

    ret[0].name = "Width";
    ret[0].type = C_STRING;
    sprintf(buf, "%d", params->w);
    ret[0].sval = dupstr(buf);
    ret[0].ival = 0;

    ret[1].name = "Height";
    ret[1].type = C_STRING;
    sprintf(buf, "%d", params->h);
    ret[1].sval = dupstr(buf);
    ret[1].ival = 0;

    ret[2].name = "No. of colours";
    ret[2].type = C_STRING;
    sprintf(buf, "%d", params->ncols);
    ret[2].sval = dupstr(buf);
    ret[2].ival = 0;

    ret[3].name = "Scoring system";
    ret[3].type = C_CHOICES;
    ret[3].sval = ":(n-1)^2:(n-2)^2";
    ret[3].ival = params->scoresub-1;

    ret[4].name = "Ensure solubility";
    ret[4].type = C_BOOLEAN;
    ret[4].sval = NULL;
    ret[4].ival = params->soluble;

    ret[5].name = NULL;
    ret[5].type = C_END;
    ret[5].sval = NULL;
    ret[5].ival = 0;

    return ret;
}

static game_params *custom_params(config_item *cfg)
{
    game_params *ret = snew(game_params);

    ret->w = atoi(cfg[0].sval);
    ret->h = atoi(cfg[1].sval);
    ret->ncols = atoi(cfg[2].sval);
    ret->scoresub = cfg[3].ival + 1;
    ret->soluble = cfg[4].ival;

    return ret;
}

static char *validate_params(game_params *params, int full)
{
    if (params->w < 1 || params->h < 1)
	return "Width and height must both be positive";

    if (params->ncols > 9)
	return "Maximum of 9 colours";

    if (params->soluble) {
	if (params->ncols < 3)
	    return "Number of colours must be at least three";
	if (params->w * params->h <= 1)
	    return "Grid area must be greater than 1";
    } else {
	if (params->ncols < 2)
	    return "Number of colours must be at least three";
	/* ...and we must make sure we can generate at least 2 squares
	 * of each colour so it's theoretically soluble. */
	if ((params->w * params->h) < (params->ncols * 2))
	    return "Too many colours makes given grid size impossible";
    }

    if ((params->scoresub < 1) || (params->scoresub > 2))
	return "Scoring system not recognised";

    return NULL;
}

/*
 * Guaranteed-soluble grid generator.
 */
static void gen_grid(int w, int h, int nc, int *grid, random_state *rs)
{
    int wh = w*h, tc = nc+1;
    int i, j, k, c, x, y, pos, n;
    int *list, *grid2;
    int ok, failures = 0;

    /*
     * We'll use `list' to track the possible places to put our
     * next insertion. There are up to h places to insert in each
     * column: in a column of height n there are n+1 places because
     * we can insert at the very bottom or the very top, but a
     * column of height h can't have anything at all inserted in it
     * so we have up to h in each column. Likewise, with n columns
     * present there are n+1 places to fit a new one in between but
     * we can't insert a column if there are already w; so there
     * are a maximum of w new columns too. Total is wh + w.
     */
    list = snewn(wh + w, int);
    grid2 = snewn(wh, int);

    do {
        /*
         * Start with two or three squares - depending on parity of w*h
         * - of a random colour.
         */
        for (i = 0; i < wh; i++)
            grid[i] = 0;
        j = 2 + (wh % 2);
        c = 1 + random_upto(rs, nc);
	if (j <= w) {
	    for (i = 0; i < j; i++)
		grid[(h-1)*w+i] = c;
	} else {
	    assert(j <= h);
	    for (i = 0; i < j; i++)
		grid[(h-1-i)*w] = c;
	}

        /*
         * Now repeatedly insert a two-square blob in the grid, of
         * whatever colour will go at the position we chose.
         */
        while (1) {
            n = 0;

            /*
             * Build up a list of insertion points. Each point is
             * encoded as y*w+x; insertion points between columns are
             * encoded as h*w+x.
             */

            if (grid[wh - 1] == 0) {
                /*
                 * The final column is empty, so we can insert new
                 * columns.
                 */
                for (i = 0; i < w; i++) {
                    list[n++] = wh + i;
                    if (grid[(h-1)*w + i] == 0)
                        break;
                }
            }

            /*
             * Now look for places to insert within columns.
             */
            for (i = 0; i < w; i++) {
                if (grid[(h-1)*w+i] == 0)
                    break;		       /* no more columns */

                if (grid[i] != 0)
                    continue;	       /* this column is full */

                for (j = h; j-- > 0 ;) {
                    list[n++] = j*w+i;
                    if (grid[j*w+i] == 0)
                        break;	       /* this column is exhausted */
                }
            }

            if (n == 0)
                break;		       /* we're done */

#ifdef GENERATION_DIAGNOSTICS
            printf("initial grid:\n");
            {
                int x,y;
                for (y = 0; y < h; y++) {
                    for (x = 0; x < w; x++) {
                        if (grid[y*w+x] == 0)
                            printf("-");
                        else
                            printf("%d", grid[y*w+x]);
                    }
                    printf("\n");
                }
            }
#endif

            /*
             * Now go through the list one element at a time in
             * random order, and actually attempt to insert
             * something there.
             */
            while (n-- > 0) {
                int dirs[4], ndirs, dir;

                i = random_upto(rs, n+1);
                pos = list[i];
                list[i] = list[n];

                x = pos % w;
                y = pos / w;

                memcpy(grid2, grid, wh * sizeof(int));

                if (y == h) {
                    /*
                     * Insert a column at position x.
                     */
                    for (i = w-1; i > x; i--)
                        for (j = 0; j < h; j++)
                            grid2[j*w+i] = grid2[j*w+(i-1)];
                    /*
                     * Clear the new column.
                     */
                    for (j = 0; j < h; j++)
                        grid2[j*w+x] = 0;
                    /*
                     * Decrement y so that our first square is actually
                     * inserted _in_ the grid rather than just below it.
                     */
                    y--;
                }

                /*
                 * Insert a square within column x at position y.
                 */
                for (i = 0; i+1 <= y; i++)
                    grid2[i*w+x] = grid2[(i+1)*w+x];

#ifdef GENERATION_DIAGNOSTICS
                printf("trying at n=%d (%d,%d)\n", n, x, y);
                grid2[y*w+x] = tc;
                {
                    int x,y;
                    for (y = 0; y < h; y++) {
                        for (x = 0; x < w; x++) {
                            if (grid2[y*w+x] == 0)
                                printf("-");
                            else if (grid2[y*w+x] <= nc)
                                printf("%d", grid2[y*w+x]);
                            else
                                printf("*");
                        }
                        printf("\n");
                    }
                }
#endif

                /*
                 * Pick our square colour so that it doesn't match any
                 * of its neighbours.
                 */
                {
                    int wrongcol[4], nwrong = 0;

                    /*
                     * List the neighbouring colours.
                     */
                    if (x > 0)
                        wrongcol[nwrong++] = grid2[y*w+(x-1)];
                    if (x+1 < w)
                        wrongcol[nwrong++] = grid2[y*w+(x+1)];
                    if (y > 0)
                        wrongcol[nwrong++] = grid2[(y-1)*w+x];
                    if (y+1 < h)
                        wrongcol[nwrong++] = grid2[(y+1)*w+x];

                    /*
                     * Eliminate duplicates. We can afford a shoddy
                     * algorithm here because the problem size is
                     * bounded.
                     */
                    for (i = j = 0 ;; i++) {
                        int pos = -1, min = 0;
                        if (j > 0)
                            min = wrongcol[j-1];
                        for (k = i; k < nwrong; k++)
                            if (wrongcol[k] > min &&
                                (pos == -1 || wrongcol[k] < wrongcol[pos]))
                                pos = k;
                        if (pos >= 0) {
                            int v = wrongcol[pos];
                            wrongcol[pos] = wrongcol[j];
                            wrongcol[j++] = v;
                        } else
                            break;
                    }
                    nwrong = j;

                    /*
                     * If no colour will go here, stop trying.
                     */
                    if (nwrong == nc)
                        continue;

                    /*
                     * Otherwise, pick a colour from the remaining
                     * ones.
                     */
                    c = 1 + random_upto(rs, nc - nwrong);
                    for (i = 0; i < nwrong; i++) {
                        if (c >= wrongcol[i])
                            c++;
                        else
                            break;
                    }
                }

                /*
                 * Place the new square.
                 * 
                 * Although I've _chosen_ the new region's colour
                 * (so that we can check adjacency), I'm going to
                 * actually place it as an invalid colour (tc)
                 * until I'm sure it's viable. This is so that I
                 * can conveniently check that I really have made a
                 * _valid_ inverse move later on.
                 */
#ifdef GENERATION_DIAGNOSTICS
                printf("picked colour %d\n", c);
#endif
                grid2[y*w+x] = tc;

                /*
                 * Now attempt to extend it in one of three ways: left,
                 * right or up.
                 */
                ndirs = 0;
                if (x > 0 &&
                    grid2[y*w+(x-1)] != c &&
                    grid2[x-1] == 0 &&
                    (y+1 >= h || grid2[(y+1)*w+(x-1)] != c) &&
                    (y+1 >= h || grid2[(y+1)*w+(x-1)] != 0) &&
                    (x <= 1 || grid2[y*w+(x-2)] != c))
                    dirs[ndirs++] = -1;    /* left */
                if (x+1 < w &&
                    grid2[y*w+(x+1)] != c &&
                    grid2[x+1] == 0 &&
                    (y+1 >= h || grid2[(y+1)*w+(x+1)] != c) &&
                    (y+1 >= h || grid2[(y+1)*w+(x+1)] != 0) &&
                    (x+2 >= w || grid2[y*w+(x+2)] != c))
                    dirs[ndirs++] = +1;    /* right */
                if (y > 0 &&
                    grid2[x] == 0 &&
                    (x <= 0 || grid2[(y-1)*w+(x-1)] != c) &&
                    (x+1 >= w || grid2[(y-1)*w+(x+1)] != c)) {
                    /*
                     * We add this possibility _twice_, so that the
                     * probability of placing a vertical domino is
                     * about the same as that of a horizontal. This
                     * should yield less bias in the generated
                     * grids.
                     */
                    dirs[ndirs++] = 0;     /* up */
                    dirs[ndirs++] = 0;     /* up */
                }

                if (ndirs == 0)
                    continue;

                dir = dirs[random_upto(rs, ndirs)];

#ifdef GENERATION_DIAGNOSTICS
                printf("picked dir %d\n", dir);
#endif

                /*
                 * Insert a square within column (x+dir) at position y.
                 */
                for (i = 0; i+1 <= y; i++)
                    grid2[i*w+x+dir] = grid2[(i+1)*w+x+dir];
                grid2[y*w+x+dir] = tc;

                /*
                 * See if we've divided the remaining grid squares
                 * into sub-areas. If so, we need every sub-area to
                 * have an even area or we won't be able to
                 * complete generation.
                 * 
                 * If the height is odd and not all columns are
                 * present, we can increase the area of a subarea
                 * by adding a new column in it, so in that
                 * situation we don't mind having as many odd
                 * subareas as there are spare columns.
                 * 
                 * If the height is even, we can't fix it at all.
                 */
                {
                    int nerrs = 0, nfix = 0;
                    k = 0;             /* current subarea size */
                    for (i = 0; i < w; i++) {
                        if (grid2[(h-1)*w+i] == 0) {
                            if (h % 2)
                                nfix++;
                            continue;
                        }
                        for (j = 0; j < h && grid2[j*w+i] == 0; j++);
                        assert(j < h);
                        if (j == 0) {
                            /*
                             * End of previous subarea.
                             */
                            if (k % 2)
                                nerrs++;
                            k = 0;
                        } else {
                            k += j;
                        }
                    }
                    if (k % 2)
                        nerrs++;
                    if (nerrs > nfix)
                        continue;      /* try a different placement */
                }

                /*
                 * We've made a move. Verify that it is a valid
                 * move and that if made it would indeed yield the
                 * previous grid state. The criteria are:
                 * 
                 *  (a) removing all the squares of colour tc (and
                 *      shuffling the columns up etc) from grid2
                 *      would yield grid
                 *  (b) no square of colour tc is adjacent to one
                 *      of colour c
                 *  (c) all the squares of colour tc form a single
                 *      connected component
                 * 
                 * We verify the latter property at the same time
                 * as checking that removing all the tc squares
                 * would yield the previous grid. Then we colour
                 * the tc squares in colour c by breadth-first
                 * search, which conveniently permits us to test
                 * that they're all connected.
                 */
                {
                    int x1, x2, y1, y2;
                    int ok = TRUE;
                    int fillstart = -1, ntc = 0;

#ifdef GENERATION_DIAGNOSTICS
                    {
                        int x,y;
                        printf("testing move (new, old):\n");
                        for (y = 0; y < h; y++) {
                            for (x = 0; x < w; x++) {
                                if (grid2[y*w+x] == 0)
                                    printf("-");
                                else if (grid2[y*w+x] <= nc)
                                    printf("%d", grid2[y*w+x]);
                                else
                                    printf("*");
                            }
                            printf("   ");
                            for (x = 0; x < w; x++) {
                                if (grid[y*w+x] == 0)
                                    printf("-");
                                else
                                    printf("%d", grid[y*w+x]);
                            }
                            printf("\n");
                        }
                    }
#endif

                    for (x1 = x2 = 0; x2 < w; x2++) {
                        int usedcol = FALSE;

                        for (y1 = y2 = h-1; y2 >= 0; y2--) {
                            if (grid2[y2*w+x2] == tc) {
                                ntc++;
                                if (fillstart == -1)
                                    fillstart = y2*w+x2;
                                if ((y2+1 < h && grid2[(y2+1)*w+x2] == c) ||
                                    (y2-1 >= 0 && grid2[(y2-1)*w+x2] == c) ||
                                    (x2+1 < w && grid2[y2*w+x2+1] == c) ||
                                    (x2-1 >= 0 && grid2[y2*w+x2-1] == c)) {
#ifdef GENERATION_DIAGNOSTICS
                                    printf("adjacency failure at %d,%d\n",
                                           x2, y2);
#endif
                                    ok = FALSE;
                                }
                                continue;
                            }
                            if (grid2[y2*w+x2] == 0)
                                break;
                            usedcol = TRUE;
                            if (grid2[y2*w+x2] != grid[y1*w+x1]) {
#ifdef GENERATION_DIAGNOSTICS
                                printf("matching failure at %d,%d vs %d,%d\n",
                                       x2, y2, x1, y1);
#endif
                                ok = FALSE;
                            }
                            y1--;
                        }

                        /*
                         * If we've reached the top of the column
                         * in grid2, verify that we've also reached
                         * the top of the column in `grid'.
                         */
                        if (usedcol) {
                            while (y1 >= 0) {
                                if (grid[y1*w+x1] != 0) {
#ifdef GENERATION_DIAGNOSTICS
                                    printf("junk at column top (%d,%d)\n",
                                           x1, y1);
#endif
                                    ok = FALSE;
                                }
                                y1--;
                            }
                        }

                        if (!ok)
                            break;

                        if (usedcol)
                            x1++;
                    }

                    if (!ok) {
                        assert(!"This should never happen");

                        /*
                         * If this game is compiled NDEBUG so that
                         * the assertion doesn't bring it to a
                         * crashing halt, the only thing we can do
                         * is to give up, loop round again, and
                         * hope to randomly avoid making whatever
                         * type of move just caused this failure.
                         */
                        continue;
                    }

                    /*
                     * Now use bfs to fill in the tc section as
                     * colour c. We use `list' to store the set of
                     * squares we have to process.
                     */
                    i = j = 0;
                    assert(fillstart >= 0);
                    list[i++] = fillstart;
#ifdef OUTPUT_SOLUTION
                    printf("M");
#endif
                    while (j < i) {
                        k = list[j];
                        x = k % w;
                        y = k / w;
#ifdef OUTPUT_SOLUTION
                        printf("%s%d", j ? "," : "", k);
#endif
                        j++;

                        assert(grid2[k] == tc);
                        grid2[k] = c;

                        if (x > 0 && grid2[k-1] == tc)
                            list[i++] = k-1;
                        if (x+1 < w && grid2[k+1] == tc)
                            list[i++] = k+1;
                        if (y > 0 && grid2[k-w] == tc)
                            list[i++] = k-w;
                        if (y+1 < h && grid2[k+w] == tc)
                            list[i++] = k+w;
                    }
#ifdef OUTPUT_SOLUTION
                    printf("\n");
#endif

                    /*
                     * Check that we've filled the same number of
                     * tc squares as we originally found.
                     */
                    assert(j == ntc);
                }

                memcpy(grid, grid2, wh * sizeof(int));

                break;		       /* done it! */
            }

#ifdef GENERATION_DIAGNOSTICS
            {
                int x,y;
                printf("n=%d\n", n);
                for (y = 0; y < h; y++) {
                    for (x = 0; x < w; x++) {
                        if (grid[y*w+x] == 0)
                            printf("-");
                        else
                            printf("%d", grid[y*w+x]);
                    }
                    printf("\n");
                }
            }
#endif

            if (n < 0)
                break;
        }

        ok = TRUE;
        for (i = 0; i < wh; i++)
            if (grid[i] == 0) {
                ok = FALSE;
                failures++;