Previous | Contents | Index | Next

Chapter 34: Signpost

You have a grid of squares; each square (except the last one) contains an arrow, and some squares also contain numbers. Your job is to connect the squares to form a continuous list of numbers starting at 1 and linked in the direction of the arrows – so the arrow inside the square with the number 1 will point to the square containing the number 2, which will point to the square containing the number 3, etc. Each square can be any distance away from the previous one, as long as it is somewhere in the direction of the arrow.

By convention the first and last numbers are shown; one or more interim numbers may also appear at the beginning.

Credit for this puzzle goes to Janko [17], who call it ‘Pfeilpfad’ (‘arrow path’).

Signpost was contributed to this collection by James Harvey.

[17] http://janko.at/Raetsel/Pfeilpfad/index.htm

34.1 Signpost controls

To play Signpost, you connect squares together by dragging from one square to another, indicating that they are adjacent in the sequence. Drag with the left button from a square to its successor, or with the right button from a square to its predecessor.

If you connect together two squares in this way and one of them has a number in it, the appropriate number will appear in the other square. If you connect two non-numbered squares, they will be assigned temporary algebraic labels: on the first occasion, they will be labelled ‘a’ and ‘a+1’, and then ‘b’ and ‘b+1’, and so on. Connecting more squares on to the ends of such a chain will cause them all to be labelled with the same letter.

When you left-click or right-click in a square, the legal squares to connect it to will be shown.

The arrow in each square starts off black, and goes grey once you connect the square to its successor. Also, each square which needs a predecessor has a small dot in the bottom left corner, which vanishes once you link a square to it. So your aim is always to connect a square with a black arrow to a square with a dot.

To remove any links for a particular square (both incoming and outgoing), left-drag it off the grid. To remove a whole chain, right-drag any square in the chain off the grid.

You can also use the cursor keys to move around the grid squares and lines. Pressing the return key when over a square starts a link operation, and pressing the return key again over a square will finish the link, if allowable. Pressing the space bar over a square will show the other squares pointing to it, and allow you to form a backward link, and pressing the space bar again cancels this.

(All the actions described in section 2.1 are also available.)

34.2 Signpost parameters

These parameters are available from the ‘Custom...’ option on the ‘Type’ menu.

Width, Height

Size of grid in squares.

Force start/end to corners

If true, the start and end squares are always placed in opposite corners (the start at the top left, and the end at the bottom right). If false the start and end squares are placed randomly (although always both shown).

/***************************************************************************
 *             __________               __   ___.
 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
 *                     \/            \/     \/    \/            \/
 * $Id$
 *
 * Copyright (C) 2004 by Dave Hooper
 *
 * This particular source code file is licensed under the X11 license. See the
 * bottom of the COPYING file for details on this license.
 *
 * Original code from http://www.beermex.com/@spc/ihpfirm.src.zip
 * Details at http://www.rockbox.org/twiki/bin/view/Main/IriverToolsGuide
 *
 ****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "iriver.h"

const unsigned char munge[] = {
  0x7a, 0x36, 0xc4, 0x43, 0x49, 0x6b, 0x35, 0x4e, 0xa3, 0x46, 0x25, 0x84,
  0x4d, 0x73, 0x74, 0x61
};

const unsigned char header_modify[] = "* IHPFIRM-DECODED ";

const char * const models[] = { "iHP-100", "iHP-120/iHP-140", "H300 series",
                                NULL };

/* aligns with models array;  expected min firmware size */
const unsigned int firmware_minsize[] = { 0x100000, 0x100000, 0x200000 };
/* aligns with models array;  expected max firmware size */
const unsigned int firmware_maxsize[] = { 0x200000, 0x200000, 0x400000 };

const unsigned char header[][16] = {
  { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
  { 0x20, 0x03, 0x08, 0x27, 0x24, 0x00, 0x02, 0x30, 0x19, 0x17, 0x65, 0x73,
    0x85, 0x32, 0x83, 0x22 },
  { 0x20, 0x04, 0x03, 0x27, 0x20, 0x50, 0x01, 0x70, 0x80, 0x30, 0x80, 0x06,
    0x30, 0x19, 0x17, 0x65 }
};

static int testheader( const unsigned char * const data )
{
    const unsigned char * const d = data+16;
    const char * const * m = models;
    int ind = 0;
    while( *m )
    {
        if( memcmp( header[ ind ], d, 16 ) == 0 )
            return ind;
        ind++;
        m++;
    };
    return -1;
}

static void modifyheader( unsigned char * data )
{
    const unsigned char * h = header_modify;
    int i;
    for( i=0; i<512; i++ )
    {
        if( *h == '\0' )
            h = header_modify;
        *data++ ^= *h++;
    };
}

static FILE * openinfile( const char * filename )
{
    FILE * F = fopen( filename, "rb" );
    if( F == NULL )
    {
        fprintf( stderr, "Couldn't open input file %s\n", filename );
        perror( "Error was " );
        exit( -1 );
    };
    return F;
}

static FILE * openoutfile( const char * filename )
{
    FILE * F = fopen( filename, "wb" );
    if( F == NULL )
    {
        fprintf( stderr, "Couldn't open output file %s\n", filename );
        perror( "Error was " );
        exit( -1 );
    };
    return F;
}

int iriver_decode(const char *infile_name, const char *outfile_name, BOOL modify,
                  enum striptype stripmode )
{
    FILE * infile = NULL;
    FILE * outfile = NULL;
    int i = -1;
    unsigned char headerdata[512];
    unsigned long dwLength1, dwLength2, dwLength3, fp = 0;
    unsigned char blockdata[16+16];
    unsigned char out[16];
    unsigned char newmunge;
    signed long lenread;
    int s = 0;
    unsigned char * pChecksums, * ppChecksums = 0;
    unsigned char ck;

    infile = openinfile(infile_name);
    outfile = openoutfile(outfile_name);

    lenread = fread( headerdata, 1, 512, infile );
    if( lenread != 512 )
    {
        fprintf( stderr, "This doesn't look like a valid encrypted iHP "
                 "firmware - reason: header length\n" );
        fclose(infile);
        fclose(outfile);
        return -1;
    };

    i = testheader( headerdata );
    if( i == -1 )
    {
        fprintf( stderr, "This firmware is for an unknown model, or is not"
                 " a valid encrypted iHP firmware\n" );
        fclose(infile);
        fclose(outfile);
        return -2;
    };
    fprintf( stderr, "Model %s\n", models[ i ] );

    dwLength1 = headerdata[0] | (headerdata[1]<<8) |
        (headerdata[2]<<16) | (headerdata[3]<<24);
    dwLength2 = headerdata[4] | (headerdata[5]<<8) |
        (headerdata[6]<<16) | (headerdata[7]<<24);
    dwLength3 = headerdata[8] | (headerdata[9]<<8) |
        (headerdata[10]<<16) | (headerdata[11]<<24);

    if( dwLength1 < firmware_minsize[ i ] ||
        dwLength1 > firmware_maxsize[ i ] ||
        dwLength2 < firmware_minsize[ i ] ||
        dwLength2 > dwLength1 ||
        dwLength3 > dwLength1 ||
        dwLength2>>9 != dwLength3 ||
        dwLength2+dwLength3+512 != dwLength1 )
    {
        fprintf( stderr, "This doesn't look like a valid encrypted "
                 "iHP firmware - reason: file 'length' data\n" );
        fclose(infile);
        fclose(outfile);
        return -3;
    };

    pChecksums = ppChecksums = (unsigned char *)( malloc( dwLength3 ) );

    if( modify )
    {
        modifyheader( headerdata );
    };

    if( stripmode == STRIP_NONE )
        fwrite( headerdata, 512, 1, outfile );

    memset( blockdata, 0, 16 );

    ck = 0;
    while( ( fp < dwLength2 ) &&
           ( lenread = fread( blockdata+16, 1, 16, infile ) ) == 16 )
    {
        fp += 16;

        for( i=0; i<16; ++i )
        {
            newmunge = blockdata[16+i] ^ munge[i];
            out[i] = newmunge ^ blockdata[i];
            blockdata[i] = newmunge;
            ck += out[i];
        }

        if( fp > ESTF_SIZE || stripmode != STRIP_HEADER_CHECKSUM_ESTF )
        {
            fwrite( out+4, 1, 12, outfile );
            fwrite( out, 1, 4, outfile );
        }
        else
        {
            if( ESTF_SIZE - fp < 16 )
            {
                memcpy( out+4, blockdata+16, 12 );
                memcpy( out, blockdata+28, 4 );
                fwrite( blockdata+16+ESTF_SIZE-fp, 1, ESTF_SIZE-fp, outfile );
            }
        }


        if( s == 496 )
        {
            s = 0;
            memset( blockdata, 0, 16 );
            *ppChecksums++ = ck;
            ck = 0;
        }
        else
            s+=16;
    };

    if( fp != dwLength2 )
    {
        fprintf( stderr, "This doesn't look like a valid encrypted "
                 "iHP firmware - reason: 'length2' mismatch\n" );
        fclose(infile);
        fclose(outfile);
        return -4;
    };

    fp = 0;
    ppChecksums = pChecksums;
    while( ( fp < dwLength3 ) &&
           ( lenread = fread( blockdata, 1, 32, infile ) ) > 0 )
    {
        fp += lenread;
        if( stripmode == STRIP_NONE )
            fwrite( blockdata, 1, lenread, outfile );
        if( memcmp( ppChecksums, blockdata, lenread ) != 0 )
        {
            fprintf( stderr, "This doesn't look like a valid encrypted "
                     "iHP firmware - reason: Checksum mismatch!" );
            fclose(infile);
            fclose(outfile);
            return -5;
        };
        ppChecksums += lenread;
    };

    if( fp != dwLength3 )
    {
        fprintf( stderr, "This doesn't look like a valid encrypted "
                 "iHP firmware - reason: 'length3' mismatch\n" );
        fclose(infile);
        fclose(outfile);
        return -6;
    };


    fprintf( stderr, "File decoded correctly and all checksums matched!\n" );
    switch( stripmode )
    {
        default:
        case STRIP_NONE:
            fprintf(stderr, "Output file contains all headers and "
                    "checksums\n");
            break;
        case STRIP_HEADER_CHECKSUM:
            fprintf( stderr, "NB:  output file contains only ESTFBINR header"
                     " and decoded firmware code\n" );
            break;
        case STRIP_HEADER_CHECKSUM_ESTF:
            fprintf( stderr, "NB:  output file contains only raw decoded "
                     "firmware code\n" );
            break;
    };

    return 0;
}

int iriver_encode(const char *infile_name, const char *outfile_name, BOOL modify )
{
    FILE * infile = NULL;
    FILE * outfile = NULL;
    int i = -1;
    unsigned char headerdata[512];
    unsigned long dwLength1, dwLength2, dwLength3, fp = 0;
    unsigned char blockdata[16+16];
    unsigned char out[16];
    unsigned char newmunge;
    signed long lenread;
    int s = 0;
    unsigned char * pChecksums, * ppChecksums;
    unsigned char ck;

    infile = openinfile(infile_name);
    outfile = openoutfile(outfile_name);

    lenread = fread( headerdata, 1, 512, infile );
    if( lenread != 512 )
    {
        fprintf( stderr, "This doesn't look like a valid decoded "
                 "iHP firmware - reason: header length\n" );
        fclose(infile);
        fclose(outfile);
        return -1;
    };

    if( modify )
    {
        modifyheader( headerdata ); /* reversible */
    };

    i = testheader( headerdata );
    if( i == -1 )
    {
        fprintf( stderr, "This firmware is for an unknown model, or is not"
                 " a valid decoded iHP firmware\n" );
        fclose(infile);
        fclose(outfile);
        return -2;
    };
    fprintf( stderr, "Model %s\n", models[ i ] );

    dwLength1 = headerdata[0] | (headerdata[1]<<8) |
        (headerdata[2]<<16) | (headerdata[3]<<24);
    dwLength2 = headerdata[4] | (headerdata[5]<<8) |
        (headerdata[6]<<16) | (headerdata[7]<<24);
    dwLength3 = headerdata[8] | (headerdata[9]<<8) |
        (headerdata[10]<<16) | (headerdata[11]<<24);

    if( dwLength1 < firmware_minsize[i] ||
        dwLength1 > firmware_maxsize[i] ||
        dwLength2 < firmware_minsize[i] ||
        dwLength2 > dwLength1 ||
        dwLength3 > dwLength1 ||
        dwLength2+dwLength3+512 != dwLength1 )
    {
        fprintf( stderr, "This doesn't look like a valid decoded iHP"
                 " firmware - reason: file 'length' data\n" );
        fclose(infile);
        fclose(outfile);
        return -3;
    };

    pChecksums = ppChecksums = (unsigned char *)( malloc( dwLength3 ) );

    fwrite( headerdata, 512, 1, outfile );

    memset( blockdata, 0, 16 );
    ck = 0;
    while( ( fp < dwLength2 ) &&
           ( lenread = fread( blockdata+16, 1, 16, infile ) ) == 16 )
    {
        fp += 16;
        for( i=0; i<16; ++i )
        {
            newmunge = blockdata[16+((12+i)&0xf)] ^ blockdata[i];
            out[i] = newmunge ^ munge[i];
            ck += blockdata[16+i];
            blockdata[i] = newmunge;
        };
        fwrite( out, 1, 16, outfile );

        if( s == 496 )
        {
            s = 0;
            memset( blockdata, 0, 16 );
            *ppChecksums++ = ck;
            ck = 0;
        }
        else
            s+=16;
    };

    if( fp != dwLength2 )
    {
        fprintf( stderr, "This doesn't look like a valid decoded "
                 "iHP firmware - reason: 'length1' mismatch\n" );
        fclose(infile);
        fclose(outfile);
        return -4;
    };

    /* write out remainder w/out applying descrambler */
    fp = 0;
    lenread = dwLength3;
    ppChecksums = pChecksums;
    while( ( fp < dwLength3) &&
           ( lenread = fwrite( ppChecksums, 1, lenread, outfile ) ) > 0 )
    {
        fp += lenread;
        ppChecksums += lenread;
        lenread = dwLength3 - fp;
    };

    if( fp != dwLength3 )
    {
        fprintf( stderr, "This doesn't look like a valid decoded "
                 "iHP firmware - reason: 'length2' mismatch\n" );
        fclose(infile);
        fclose(outfile);
        return -5;
    };

    fprintf( stderr, "File encoded successfully and checksum table built!\n" );

    fclose(infile);
    fclose(outfile);
    return 0;
}