128 - Software CRC

[Maarten]

I'm just wondering, how do people get those *really* low execution times ? For example in problem 128, the program runs in 0.6 seconds, but the fastest solution in 0.06 seconds, which is about 10 times faster! There might be some optimization possible on my code, but I'm quite convinced there's not THAT much to gain! After all, I have to read all the input at least once...

btw, my code is:

[cpp]
#include <stdio.h>

#define LONG unsigned long

int main(int argc, char *argv[])
{
LONG g = 34943;
char line[1025];
while( gets(line) != NULL ) {
if( line[0] == '#' ) break;
LONG message = 0, pos = 0;
while( line[pos] != 0 )
message = ((message<<8) + line[pos++])%g;
message = (message<<16)%g;
LONG crc = (g - message)%g;
printf( "%02X %02X\n", (crc & 0xFF00)>>8, crc & 0xFF );
}
return 0;
}
[/cpp]

[zaghaghi]

you can set the ios::uppercase flag for cout.
you can use setf member function of cout to set this flag :

[cpp]
cout.fill('0');
cout.setf(ios::uppercase);
cout<<hex<<setw(2)<<nHigherByteCRC<<" ";
cout<<hex<<setw(2)<<nLowerByteCRC <<" "<<endl;
[/cpp]

and for unsetting this flag use unsetf member function of cout.

[chicapi]

They always have a trick.

You should have noticed that hexa numbers in the output are in UPPER case and C printfs them is lower case...

then you get AC!!

[Corpse Fiend]

Can someone explain the "generating CRC - for dummies" algorithm? I can't understand it. :|

[Dominik Michniewski]

to chicapi:
read carefully manual for printf() function - exist flag to output hexadecimal numbers in uppercase

Bes regards
DM

[bowman]

Hi,

given all I know about CRC calculation and the Polynomial p = 0x887F (34943 in decimal), I cannot verify the example data. No matter if I use a program or pen and paper, I get 0x3643 as the CRC for "A".

Am I doing something wrong or is the example data incorrect?

I will NOT calculate the CRC of "this is a test" on paper!

[Stas]

Hi,

you can verify the example data like this:

m = "A" = 65 decimal = 0100 0001

"2" = 0x0C86 = "0000 1100 1000 0110"


g = 34943 decimal = 1000 1000 0111 1111

The CRC value is chosen so that ``m2'' when divided by a certain 16-bit value ``g'' leaves a remainder of 0.

so,

0100 0001(m) 0000 1100 1000 0110(2) % 1000 1000 0111 1111(g) = 0
(division result is 1111010 = 122,0 decimal)

[Andrey]

I don't understand the explanation for this problem!!

Please help me!!

Sorry for my english!!

[BlackDevil]

Please can any body explain the CRC problem.................. and if there cases to test ot????????????

[ar2rd]

I have no idea what's wrong with my code. Does anybody have some special cases or other inputs. Here is my code:

Code: Select all

// Software CRC - acm.uva.es/p/v1/128.cpp
// by Artur Dmowski
#include <cstdio>
#include <cstring>
#define G 34943
using namespace std;

char line[1500];
int crc,m,k,i;

int main() {
   #ifndef ONLINE_JUDGE 
     freopen("in.txt","r",stdin);
     freopen("out.txt","w",stdout);
   #endif
   
   while( gets(line) ) { 
    
    if( line[0] == '#' ) return 0;
    
    m = 0;
    k = strlen(line);
    
    for(i = 0; i < k; i++) 
         m = ((m<<8)+line[i])%G; 
    
    m = (m<<16)%G;
    crc = (m==0 ? 0 : G-m);
    
    printf("%02X %02X\n", crc>>8, crc -((crc>>8)<<8));
   }
}

[MeteorRain]

YEA, Also WA'ed. could anyone give some test case or give some advices? thanks in advance.

Code: Select all

// uva128 Software CRC
// MR

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

int main()
{
	char str[1040];
	int pos, curr, sl, out;
	while(1)
	{
		gets(str);
		if(str[0] == '#')
			break;
		pos = 1;
		curr = str[0];
		sl = strlen(str);
		while(pos < sl)
			curr = (curr << 8 + str[pos++]) % 34943;
		out = (34943 - (curr << 16) % 34943) % 34943;
		printf("%02X %02X\n", out >> 8, out % 256);
	}
	return 0;
}

[Darko]

Hm, for me that C code doesn't produce correct answer for the sample input.

Seems that strlen() counts the newline character. But even if I ignore the last character, it still doesn't output right answer for an empty string. After fixing that, it's still broken. (although it passes sample input at that point)

I don't know C, so I don't know why compiler complains about gets() and shift operations not being inside parenthesis (I put them inside, but that didn't work).

Darko

[chunyi81]

Darko: gets discards the newline character.

MeteorRain:
This code:

Code: Select all

      while(pos < sl) 
         curr = (curr << 8 + str[pos++]) % 34943; 

works differently from this code:

Code: Select all

      while(pos < sl) 
         curr = ((curr << 8) + str[pos++]) % 34943; 

in my gcc 3.3.2 compiler.

Changing to the second code will make your code work with the sample input.

[Darko]

Darko: gets discards the newline character.

My bad - I copied the file from Windows - it had carriage returns at the end.

But it stil gave me a wrong answer for the empty string, even with shift in parenthesis. (gcc 3.4.3)

I couldn't see why it wouldn't work afterwards.. but it didn't.

Darko

[chunyi81]

The empty string still gives me correct output on my university's Unix server for MeteorRain's code, after putting the shift in parantheses.

This test case from a past thread will reveal the error in both WA programs in this thread:

Input:

Code: Select all

RFC: 793
#

ar2rd's program output:

Code: Select all

10A 21

MeteorRain's program output:

Code: Select all

81 A2

But correct output should be:

Code: Select all

0A 21