My entry for the IndieVault Code Contest 01 ( http://www.indievault.it/forum/showthread.php?tid=9536 )

CMakeLists.txt

cmake_minimum_required (VERSION 2.6) 

project (ivcc01_thecrib) 

if(MSVC) #((((((((((((((((
 set(CMAKE_C_FLAGS_RELEASE   "/DNDEBUG /DWIN32     /MD  /Ox /Ot /Oi /GL /Ob2 /Oy /arch:SSE2")
 set(CMAKE_CXX_FLAGS_RELEASE "/DNDEBUG /DWIN32     /MD  /Ox /Ot /Oi /GL /Ob2 /Oy /arch:SSE2")
 set(CMAKE_C_FLAGS_DEBUG     "/D_DEBUG /DWIN32 /Zi /MDd /Od                      /arch:SSE2")
 set(CMAKE_CXX_FLAGS_DEBUG   "/D_DEBUG /DWIN32 /Zi /MDd /Od                      /arch:SSE2")
 add_definitions( "/D_CRT_SECURE_NO_WARNINGS /wd4996 /nologo" ) # disable annoying secure CRT warnings
 add_definitions( "/GR-" ) # disable RTTI
else() #--------------------
 set(CMAKE_C_FLAGS_RELEASE   "-DNDEBUG")
 set(CMAKE_CXX_FLAGS_RELEASE "-DNDEBUG  -std=c++0x")
 set(CMAKE_C_FLAGS_DEBUG     "-D_DEBUG")
 set(CMAKE_CXX_FLAGS_DEBUG   "-D_DEBUG  -std=c++0x")
endif() #))))))))))))))))

add_executable (ivcc01_thecrib ivcc01_thecrib.cpp)

ivcc01_thecrib.cpp

//==================================================================
/// ivcc01_thecrib.cpp
///
/// Created by Davide Pasca - 2013/7/15
/// 
/// 
//==================================================================

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

#if defined(_MSC_VER)
# include <Windows.h>
typedef unsigned __int8 uint8_t;
typedef unsigned __int16 uint16_t;
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
#else
# include <stdint.h>
# include <sys/time.h>
#endif

// program tweaks
#define USED_EOL          '\n'
#define MAX_MOVES         24    // must be multiple of 4
#define MAX_MOVE_NAME_LEN 32
#define MAX_MOVE_DEF_LEN  64
#define WRITE_BUFF_SIZE   (1024*1024*2)

#if defined(_MSC_VER)
# define USE_MMAP_FOR_READ    // Read option (comment to use fread)
//# define USE_MMAP_FOR_WRITE   // Write option for memory mapping
# define USE_WIN_ASYNC_WRITE  // Write option for async writes

# if defined(USE_MMAP_FOR_WRITE) && defined(USE_WIN_ASYNC_WRITE)
#  error "Please, define only one or no options for writing"
# endif
#endif

// uncomment below to get profiling output
#define PROFBEGIN(_P_,_X_)  //QuickProf _prof##_P_; _prof##_P_.Begin(_X_)
#define PROFEND(_P_)        //_prof##_P_.End()

#if defined(_MSC_VER)
# define DFORCEINLINE __forceinline
#else
# define DFORCEINLINE inline __attribute__((always_inline))
#endif

//==================================================================
static void ExitErr( const char *pMsg )
{
    puts( pMsg );
    exit( -1 );
}

//==================================================================
DFORCEINLINE double TimerGetMS()
{
#if defined(_MSC_VER)
    static double coe;
    static bool isInitialized;
    if ( !isInitialized )
    {
        isInitialized = true;
        __int64 freq;
        QueryPerformanceFrequency( (LARGE_INTEGER *)&freq );
        coe = 1000.0 / freq;
    }

    __int64 val;
    QueryPerformanceCounter( (LARGE_INTEGER *)&val );
    return val * coe;
#else
    timeval timeVal;
    gettimeofday( &timeVal, NULL );
    return (double)timeVal.tv_sec * 1000.0 + (double)timeVal.tv_usec;
#endif
}

//==================================================================
class QuickProf
{
    const char  *mpMsg;
    double      mStart;
public:
    void Begin( const char *pMsg ) {
        mpMsg = pMsg;
        mStart = TimerGetMS();
    }

    void End() {
        double elapsed = TimerGetMS() - mStart;
        printf( "%s: %4.2lf ms\n", mpMsg, elapsed );
    }
};

//==================================================================
class ReadBuff
{
#if defined(USE_MMAP_FOR_READ)
    HANDLE  mhFile;
#endif
    size_t  mSize;
    char    *mpData;
    size_t  mIdx;
public:
    ReadBuff( const char *pFName, size_t zeroPadLen )
        : mSize(0)
        , mpData(nullptr)
        , mIdx(0)
    {
#if defined(USE_MMAP_FOR_READ)
        mhFile = CreateFile(
                    pFName,
                    GENERIC_READ,
                    0, NULL,
                    OPEN_EXISTING,
                    FILE_ATTRIBUTE_READONLY,
                    NULL );

        if ( !mhFile )
            ExitErr( "Couldn't open the file for reading" );

        mSize = GetFileSize( mhFile, NULL );

        HANDLE handle = 
            CreateFileMapping( mhFile, NULL, PAGE_READONLY, 0, mSize, 0 );

        if ( !handle )
            ExitErr( "Couldn't setup the file mapping for reading" );

        mpData = (char *)MapViewOfFile(handle,FILE_MAP_READ,0,0,mSize);
        CloseHandle(handle);
#else
        FILE *fp = fopen( pFName, "rb" );
        if ( !fp )
            ExitErr( "Couldn't open the file for reading" );

        fseek( fp, 0, SEEK_END );
        mSize = ftell( fp );
        fseek( fp, 0, SEEK_SET );
        mpData = (char *)malloc( mSize+zeroPadLen );
        if ( mSize != (size_t)fread( mpData, 1, mSize, fp ) )
            ExitErr( "Problems reading" );

        // zero padding to avoid extra checks
        memset( mpData + mSize, 0, zeroPadLen );

        fclose( fp );
#endif
    }

    ~ReadBuff()
    {
#if defined(USE_MMAP_FOR_READ)
        UnmapViewOfFile( mpData );
        CloseHandle( mhFile );
#else
        free( mpData );
#endif
    }

    const char *GetDataCur() const { return mpData + mIdx; }
    const char *GetDataEnd() const { return mpData + mSize; }

    size_t GetSize() const { return mSize; }

    const char *NextLine()
    {
        size_t staIdx = mIdx;

        while ( mpData[ mIdx ] != USED_EOL && mpData[ mIdx ] )
            ++mIdx;

        ++mIdx;

        return &mpData[ staIdx ];
    }
};

//==================================================================
static const size_t MEMCPYBLK_PAD = 8;
//==================================================================
// limited to 32 bytes.. ideal for the moves' names
DFORCEINLINE void memcpyblk_s( char *pDes, const char *pSrc, size_t len )
{
    auto *pDes64 = (uint64_t *)pDes;
    auto *pSrc64 = (const uint64_t *)pSrc;
    switch ( (len + 7) >> 3 )
    {
    case 4: pDes64[3] = pSrc64[3];
    case 3: pDes64[2] = pSrc64[2];
    case 2: pDes64[1] = pSrc64[1];
    case 1: pDes64[0] = pSrc64[0];
    }
}
//==================================================================
DFORCEINLINE void memcpyblk( char *pDes, const char *pSrc, size_t len )
{
    auto *pDes64 = (uint64_t *)pDes;
    auto *pSrc64 = (const uint64_t *)pSrc;
    size_t lenblk = (len + 7) >> 3;
    for (size_t i=0; i != lenblk; ++i)
        pDes64[i] = pSrc64[i];
}

#if defined(USE_MMAP_FOR_WRITE)
//==================================================================
// Memory mapped writer
//==================================================================
class WriteBuff
{
    HANDLE      mhFile;
    char        *mpData;
    size_t      mMaxSize;
    size_t      mCurPos;

public:
    WriteBuff( const char *pFName, size_t maxSize )
        : mhFile(nullptr)
        , mpData(nullptr)
        , mMaxSize(maxSize)
        , mCurPos(0)
    {
        mhFile = CreateFile(
                    pFName,
                    GENERIC_READ | GENERIC_WRITE,
                    0, NULL,
                    CREATE_ALWAYS,
                    FILE_ATTRIBUTE_NORMAL,
                    NULL );

        setFileSize( mMaxSize );

        HANDLE handle = 
            CreateFileMapping( mhFile, NULL, PAGE_READWRITE, 0, mMaxSize, 0 );

        if ( !handle )
        {
            DWORD err = GetLastError();
            ExitErr( "Couldn't setup for write" );
        }

        mpData = (char *)MapViewOfFile( handle,FILE_MAP_WRITE,0,0,mMaxSize );
        CloseHandle(handle);
    }

    ~WriteBuff()
    {
        UnmapViewOfFile( mpData );
        setFileSize( mCurPos );
        CloseHandle( mhFile );
    }

    DFORCEINLINE void WriteLine( const char *pSta, const char *pEnd )
    {
        size_t len = pEnd - pSta;
        if ( (mCurPos+len+1+MEMCPYBLK_PAD) > mMaxSize )
            ExitErr( "Bad size in write !" );

        memcpyblk( mpData + mCurPos, pSta, len );
        mpData[mCurPos + len] = USED_EOL;
        mCurPos += len + 1;
    }

    DFORCEINLINE void WriteString( const char *pSta, size_t len )
    {
        if ( (mCurPos+len+MEMCPYBLK_PAD) > mMaxSize )
            ExitErr( "Bad size in write !" );

        memcpyblk( mpData + mCurPos, pSta, len );
        mCurPos += len;
    }
    DFORCEINLINE void WriteStringS( const char *pSta, size_t len )
    {
        if ( (mCurPos+len+MEMCPYBLK_PAD) > mMaxSize )
            ExitErr( "Bad size in write !" );

        memcpyblk_s( mpData + mCurPos, pSta, len );
        mCurPos += len;
    }
private:
    void setFileSize( size_t size )
    {
        DWORD ptrLow = SetFilePointer( mhFile, size, NULL, FILE_BEGIN );
        if ( ptrLow == INVALID_SET_FILE_POINTER )
            ExitErr( "Failed to resize the file" );
        
        if ( !SetEndOfFile( mhFile ) )
            ExitErr( "Failed to resize the file" );
    }
};
#elif defined(USE_WIN_ASYNC_WRITE)
//==================================================================
// Asynchronous double buffered writer with "overlapped"
//==================================================================
class WriteBuff
{
    HANDLE      mhFile;
    size_t      mCurPos;
    size_t      mMaxBlockSize;
    size_t      mCurBlockPos;
    char        *mpData;
    char        *mpCurData;
    OVERLAPPED  mOverlap;
    size_t      mBuffIdx;

public:
    WriteBuff( const char *pFName, char *pData, size_t maxSize )
        : mhFile(nullptr)
        , mCurPos(0)
        , mMaxBlockSize(maxSize / 2)
        , mCurBlockPos(0)
        , mpData(pData)
        , mpCurData(pData)
        , mBuffIdx(0)
    {
        mhFile = CreateFile(
                    pFName,
                    GENERIC_WRITE,
                    0, NULL,
                    CREATE_ALWAYS,
                    FILE_ATTRIBUTE_NORMAL | FILE_FLAG_OVERLAPPED,
                    NULL );

        memset( &mOverlap, 0, sizeof(mOverlap) );
    }

    ~WriteBuff()
    {
        FlushAndClose();
    }

    void FlushAndClose()
    {
        if ( !mhFile )
            return;

        Flush();

        // wait for the final flush
        waitWrite();

        CloseHandle( mhFile );
        mhFile = nullptr;
    }

    DFORCEINLINE void WriteLine( const char *pSta, const char *pEnd )
    {
        size_t len = pEnd - pSta;
        if ( (mCurBlockPos+len+1 + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk( mpCurData + mCurBlockPos, pSta, len );
        mpCurData[mCurBlockPos + len] = USED_EOL;
        mCurBlockPos += len + 1;
    }

    DFORCEINLINE void WriteString( const char *pSta, size_t len )
    {
        if ( (mCurBlockPos+len + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk( mpCurData + mCurBlockPos, pSta, len );
        mCurBlockPos += len;
    }

    DFORCEINLINE void WriteStringS( const char *pSta, size_t len )
    {
        if ( (mCurBlockPos+len + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk_s( mpCurData + mCurBlockPos, pSta, len );
        mCurBlockPos += len;
    }

    void Flush()
    {
        waitWrite();

        mOverlap.Offset = (DWORD)mCurPos;

        BOOL done = WriteFile( mhFile, mpCurData, mCurBlockPos, NULL, &mOverlap );
        if ( !done && GetLastError() != ERROR_IO_PENDING )
            ExitErr( "Problems writing (W)" );

        mCurPos += mCurBlockPos;

        mBuffIdx ^= 1;
        mpCurData = mpData + mBuffIdx * mMaxBlockSize;

        mCurBlockPos = 0;
    }
private:
    void waitWrite()
    {
        DWORD bytesDone;
        if ( !GetOverlappedResult( mhFile, &mOverlap, &bytesDone, TRUE ) )
            ExitErr( "Problems writing (O)" );
    }
};
#else
//==================================================================
// Basic writer with fread()
//==================================================================
class WriteBuff
{
    FILE        *mFP;
    size_t      mMaxBlockSize;
    char        *mpData;
    size_t      mCurBlockPos;
public:
    WriteBuff( const char *pFName, char *pData, size_t maxSize )
        : mpData(pData)
        , mMaxBlockSize(maxSize)
        , mCurBlockPos(0)
    {
        mFP = fopen( pFName, "wb" );
    }

    ~WriteBuff() { Flush(); fclose( mFP ); }

    DFORCEINLINE void WriteLine( const char *pSta, const char *pEnd )
    {
        size_t len = pEnd - pSta;
        if ( (mCurBlockPos+len+1 + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk( mpData + mCurBlockPos, pSta, len );
        mpData[mCurBlockPos + len] = USED_EOL;
        mCurBlockPos += len + 1;
    }

    DFORCEINLINE void WriteString( const char *pSta, size_t len )
    {
        if ( (mCurBlockPos+len + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk( mpData + mCurBlockPos, pSta, len );
        mCurBlockPos += len;
    }

    DFORCEINLINE void WriteStringS( const char *pSta, size_t len )
    {
        if ( (mCurBlockPos+len + MEMCPYBLK_PAD) > mMaxBlockSize )
            Flush();

        memcpyblk_s( mpData + mCurBlockPos, pSta, len );
        mCurBlockPos += len;
    }

    void Flush()
    {
        fwrite( mpData, 1, mCurBlockPos, mFP );
        mCurBlockPos = 0;
    }
};
#endif

//==================================================================
class MoveDef
{
public:
    size_t  mNameLen;
    uint8_t mDefLen;
    char    mName[MAX_MOVE_NAME_LEN];
    char    mDef[MAX_MOVE_DEF_LEN];
public:
    void Init( const char *pLine )
    {
        const char *pEndName = strchr( pLine, ':' );
        const char *pEndDef = strchr( pLine, USED_EOL );

        mDefLen = pEndDef - (pEndName+1);
        memcpy( mDef, pEndName+1, mDefLen );
        mDef[mDefLen] = 0;

        size_t nameLen = pEndName - pLine;
        memcpy( mName, pLine, nameLen );
        mName[nameLen+0] = USED_EOL; // include EOL in the name
        mName[nameLen+1] = 0;
        mNameLen = nameLen + 1;
    }
};

//==================================================================
class MinMovIdx
{
    // needs less than 256, but anyway..
    static uint8_t msCharToID[256];

    static const size_t BITS_N = 4;
    // this is a map of the lowest move index matched by the
    // an index formed of a string of 4 symbols
    uint8_t  mMinIdxMap[ 1 << (BITS_N*4) ];
    // NOTE: because there are 13 symbols, the smallest map would be
    //  of 13^4 elements, but for performance reasons we round to 16
    //  elements, so that an index can be formed with shifts instead
    //  of muls (still, we could simply allocate 13 * 16^3  instead
    //  of 16^4, but is has little effect on size (52K vs 64K) and
    //  none on performance)
public:
    MinMovIdx()
    {
        msCharToID['d'] = 0;
        msCharToID['D'] = 1;
        msCharToID['u'] = 2;
        msCharToID['U'] = 3;
        msCharToID['l'] = 4;
        msCharToID['L'] = 5;
        msCharToID['r'] = 6;
        msCharToID['R'] = 7;
        msCharToID['k'] = 8;
        msCharToID['K'] = 9;
        msCharToID['p'] = 10;
        msCharToID['P'] = 11;
        msCharToID['#'] = 12;

        // initialize to the highest index possible
        for (size_t i=0; i != _countof(mMinIdxMap); ++i)
            mMinIdxMap[i] = 0xff;
    }

    void AddMove( const char *pDef, size_t movIdx )
    {
        // update the map with the minimum move index
        auto &mapVal = mMinIdxMap[ MakeIdx( pDef ) ];
        if ( movIdx < mapVal )
            mapVal = (uint8_t)movIdx;
    }

    DFORCEINLINE uint16_t GetMinIdx( uint16_t idx ) const
    {
        return mMinIdxMap[ idx ];
    }

    // progressive index update, one character at the time
    // (faster than MakeIdx)
    static DFORCEINLINE void UpdateIdx( uint16_t &idx, char ch )
    {
        idx <<= BITS_N;
        idx |= msCharToID[ ch ];
    }

    // full index update, using whole 4 characters
    static DFORCEINLINE uint16_t MakeIdx( const char *pStr )
    {
        return (uint16_t)(
            (u_int)msCharToID[ pStr[3] ] << (0*BITS_N) |
            (u_int)msCharToID[ pStr[2] ] << (1*BITS_N) |
            (u_int)msCharToID[ pStr[1] ] << (2*BITS_N) |
            (u_int)msCharToID[ pStr[0] ] << (3*BITS_N));
    }
};
//
uint8_t MinMovIdx::msCharToID[256];

//==================================================================
int main( int argc, char *argv[] )
{
    PROFBEGIN( total, "Total run" );
{
    PROFBEGIN( read, "Reading" );
    const char *pInFName = (argc >= 2 ? argv[1] : "input.txt");
    ReadBuff read( pInFName, MAX_MOVE_DEF_LEN );
    PROFEND( read );

    MoveDef    moves[MAX_MOVES];
    size_t     movesN = 0;
    MinMovIdx  minMovIdx;

    // parse the moves
    for(const char *pLine = read.NextLine();
                    pLine[0] != USED_EOL;
                    pLine = read.NextLine())
    {
        auto &mov = moves[ movesN ];

        mov.Init( pLine );

        minMovIdx.AddMove( mov.mDef, movesN );

        movesN += 1;
    }

    // setup for writing
    const char *pOutFName = (argc >= 3 ? argv[2] : "output.txt");
#if defined(USE_MMAP_FOR_WRITE)
    // for memory mapping in output we preallocate a file
    // that is 1.5 times the one in input.. it seems reasonable
    size_t maxOutSize = (read.GetSize() + 1024) * 3 / 2;
    WriteBuff write( pOutFName, maxOutSize );
#else
    static char writeBuffData[ WRITE_BUFF_SIZE ];
    WriteBuff write( pOutFName, writeBuffData, WRITE_BUFF_SIZE );
#endif

    PROFBEGIN( scan, "Scanning" );
    // NOTE: the loop assumes some padding, which is allocated
    //  in the case of standard read, but potentially problematic
    //  with file mem mapping.
    //  It works in practice, but for exact bounding, code would
    //  become more complex (though just as fast)
    const char *pDataSta = read.GetDataCur();
    const char *pDataEnd = read.GetDataEnd();
    const char *pLastMoveEnd = pDataSta;
    auto mapIdx = MinMovIdx::MakeIdx( pDataSta );
    for (const char *pCh=pDataSta; pCh != pDataEnd; ++pCh)
    {
        size_t fromMovIdx = minMovIdx.GetMinIdx( mapIdx );

        // start looking for all moves, starting from the 1st
        // possible match..
        for (size_t i=fromMovIdx; i < movesN; ++i)
        {
            const auto &mov = moves[ i ];
            const char *pDefSrc = mov.mDef;
            size_t len = mov.mDefLen;
            for (size_t j=0; pDefSrc[j] == pCh[j]; ++j)
            {
                if ( (j+1) == len ) // found ?
                {
                    // write out
                    write.WriteLine( pLastMoveEnd, pCh );
                    write.WriteStringS( mov.mName, mov.mNameLen );

                    pLastMoveEnd = pCh + len;
                    pCh = pLastMoveEnd - 1;
                    mapIdx = MinMovIdx::MakeIdx( pCh );
                    i = movesN; // ends the loop, faster than "goto"
                    break;
                }
            }
        }
        MinMovIdx::UpdateIdx( mapIdx, pCh[4] );
    }
    PROFEND( scan );

    write.WriteString( pLastMoveEnd, pDataEnd-pLastMoveEnd );

#if defined(USE_WIN_ASYNC_WRITE)
    // explicitly flush and close the file while the write
    // buffer is still allocated (though it should probably
    // be ok to leave it to the destructor)
    write.FlushAndClose();
#endif
}
    PROFEND( total );
}

make_build.bat

mkdir _cm_build
cd _cm_build

cmake ..

cd ..