[Tävling] Programmerare

       matricks   175.193775 ms   Passed
            ice   179.987680 ms   Passed
     psionicist   291.940735 ms   Passed
          vg132   324.199863 ms   Passed
           ookk   339.116843 ms   Passed
          madah   363.781710 ms   Passed
         sunray   405.471366 ms   Passed
          etono   418.461564 ms   Passed
         eighty   400.709587 ms   Passed
          micke   465.012732 ms   Passed

     don_tomaso   347.960146 ms   Failed

Test Source

          Name     Opteron 242        P4             P4 Opt       
       matricks   174.947095 ms   216.885945 ms   119.306504 ms   Source
            ice   180.564569 ms   167.446421 ms   150.565784 ms   Source
     psionicist   292.634678 ms   227.442035 ms   215.746135 ms   Source
          vg132   324.636232 ms   272.374282 ms   248.200260 ms   Source
           ookk   336.539979 ms   264.661011 ms   269.197901 ms   Source
          madah   363.856580 ms   307.051595 ms   248.140755 ms   Source
         eighty   396.796241 ms   275.758511 ms   268.071780 ms   Source
         sunray   403.229461 ms   312.517094 ms   271.837342 ms   Source
          etono   417.711190 ms   221.111901 ms   221.471444 ms   Source
          micke   458.879550 ms   353.592426 ms   354.795651 ms   Source
     don_tomaso   426.084600 ms   477.967451 ms   449.259054 ms   Source
           cide  4739.216856 ms  4142.804463 ms  4068.235767 ms   Source

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

unsigned int get_index( const char *s )
{
	unsigned int i = 1;
	while( *s )	
	{
		i = i << 1;
		if( *s == '-' ) i = i | 1;
		s++;	
	}
	return i;
}

int main(int argc, char * argv[] )
{
	char * morse_text = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,?"; 
	char *	morse_code_array[] = {
		".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--",
		"-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--..",
		"-----",".----","..---","...--","....-",".....","-....","--...","---..","----.",
		".-.-.-","--..--","..--..",NULL};						
	int index_array[117] = {0};

	int i;
	for(i=0; morse_code_array[i]; ++i)
	{		
		index_array[ get_index( morse_code_array[i] ) ] = morse_text[i] ;
	}

	printf("const char morsetable[] = \"");	

	for(i=0; i<116; ++i)
	{
		if( index_array[i] == 0 )
			putchar( ' ' );
		else
			putchar( index_array[ i ]);			
	}
	printf("\";\n");
	return 0;
}

Okej, hela min algorithm bygger på något man kallar LUT (Lookup Table). Det
är en gammal teknik som använts mycket inom demo kodande. Det hela går ut
på att försöka räkna ut så mycket som möjligt i förväg så man slipper sedan
räkna samma sak flera gånger. Det är en klassisk memory <-> cpu tradeoff.
Man tjänar i cputid men förlorar minnet på det.

Nu kommer jag plocka ner detta på en mindre skala så det blir lättare att förstå.
Säg att vi har ett mycket mindre alphabet där max längden är 2.

. = a
- = b
.. = c
-. = d
.- = e
-- = f

Så för att exakt veta vilket kod det är som kommer så måste vi minst läsa
2st morsetecken framåt. Då finns det dessa som vi kan stöta på

"  " space
". " a
"- " b
".." c
"-." d
".-" e
"--" f

Så för att koda-av så ser det ut så här (halv c++ pseudo kod):

int loopnr = 1
while(*pSrc)
{
	c = hämtatvåtecken(pSrc)
	switch(c)
	{
	case "  ": *pDst++ = ' '; pSrc += 2; break;
	case ". ": *pDst++ = 'A'; pSrc += 2; break;
	case "- ": *pDst++ = 'B'; pSrc += 2; break;
	case "..": *pDst++ = 'C'; pSrc += 3; break;
	case "-.": *pDst++ = 'D'; pSrc += 3; break;
	case ".-": *pDst++ = 'E'; pSrc += 3; break;
	case "--": *pDst++ = 'F'; pSrc += 3; break;
	}
	loopnr++;
}


---- exempel

". - - -.   -- . -."  << pSrc
 1122334445566677888  << loop nummer
 A B B D  _ F  A D    << pDst

Så när han läser F och D så plockar han bprt lite extra




Problemet med denna kod är att den där switchen inte funkar. Man skulle
behöva göra en massa strcmp och allt skulle gå jätte slött. Svart på det
hela är att ifrån dom två tecknen vi har skapa ett index nummer. Vi
har tre möjliga tecken vi kan stöta på. space . och -. Låt oss sätta
nummer på dessa. Jag upptäckte efter att ha studerat en asciitabell att man
kunde göra detta väldigt snabbt genom denna teknik:

char  dec    bin
sp    32    100000b
-     45    101101b
.     46    101110b

Observera dom två bakersta bitarna i varje tecken.

100000b&0x3 = 00b = 0
101101b&0x3 = 01b = 1
101110b&0x3 = 10b = 2

Smidigt! Detta ger oss:

sp = 0
-  = 1
.  = 2

Att spara ett morsetecken tar asså 2bit och eftersom vi läser skall
koda av 2st samtidigt små får vi ett index på 4bitar. Vi kan sätta
ihop dessa två morsetecken på detta sätt:

int index = (pSrc[0]&0x3)|((pSrc[1]&0x3)<<2);

Nu kommer index vara från 0-8 och motsvara något av dom följande
alternativen:

nr code char     morselen
 0 "  " space    2
 1 ". " a        2
 2 "- " b        2
 3 " ." Invalid  0
 4 ".." c        3
 5 "-." d        3
 6 " -" Invalid  0
 7 ".-" e        3
 8 "--" f        3

Två av dessa är som sagt ogiltiga och dom kommer vi aldrig få upp
om inkommande data är korrekt. Sedan är morselen alltid ett
större än antalet morsetecken eftersom vi måste äta upp
spacetecknet efter varje morsekod också. Vi har nu skapat våran
LUT som då ser ut:

const int aCharLUT[] = {' ','a','b',0,'c','d',0,'e','f'};
const int aLenLUT[] = {2,2,2,0,3,3,0,3,3};

Vi kan nu koda av på detta vis:

while(*pSrc)
{
	int index = (pSrc[0]&0x3)|((pSrc[1]&0x3)<<2);
	*pDst++ = aCharLUT[index];
	pSrc += aLenLUT[index];
}

VACKERT! Eftersom vi inte har några if-satser alls så slipper vi
branch-prediction fel som kan stalla CPUn och ta en massa tid.
Ända problemet just nu är att vi kommer få massa onödiga cache
missar efter vi har två onödigt stora array. Vi kan slå ihop dom på
detta sätt:

const int aLUT[] = {
	' '|(2<<8),
	'a'|(2<<8),
	'b'|(2<<8),
	  0,
	'c'|(3<<8),
	'd'|(3<<8),
	  0,
	'e'|(3<<8),
	'f'|(3<<8)};

Och koda av genom:

while(*pSrc)
{
	int c = aLUT[  (pSrc[0]&0x3)|((pSrc[1]&0x3)<<2) ];
	*pDst++ = c&0xff;
	pSrc += c>>8;
}

Jämför ni den där funktionen med den i source koden så är dom
relativt lika bara det att den andra jobbar på 6st istället för 2st.
Sedan skrev jag givetvis koden för att generera den stora LUT:en
som finns med i filen.

(0 * 2 + 2)
((0 * 2 + 2) * 2 + 1)
(((0 * 2 + 2) * 2 + 1)) * 2 + 2) = 12

for(i=0; i < 3; i++)
{
    if( p[i] == '.' ) // . -> gå höger +2
        id = 2*id + 2;
    else // - -> gå vänster +1
        id = 2*id + 1;
}

id = (id + id) + (*p - 45 + 1);