128 - Software CRC

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

problem 128 + general question about speed

Post by 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
New poster
Posts: 2
Joined: Thu Oct 30, 2003 3:19 am
Location: IRAN
Contact:

Post by 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
New poster
Posts: 6
Joined: Thu Apr 24, 2003 9:08 pm
Location: Buenos Aires

from Presentation Error to Accepted...

Post by 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!! :D
maru 3.1415926

Corpse Fiend
New poster
Posts: 5
Joined: Wed Dec 17, 2003 6:18 pm
Location: Poland

Post by Corpse Fiend »

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

Bes regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

bowman
New poster
Posts: 2
Joined: Fri Aug 27, 2004 2:49 am

128 (CRC) - example data

Post by 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
New poster
Posts: 5
Joined: Sat Jul 03, 2004 5:15 pm
Location: Kyrgyzstan
Contact:

Post by 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
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

Problem 128!!!! Software CRC!!!

Post by Andrey »

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

Please help me!!

Sorry for my english!!
:oops: :oops: :oops:

BlackDevil
New poster
Posts: 1
Joined: Mon Oct 24, 2005 5:54 pm

CRC problem

Post by BlackDevil »

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

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am

128-Software CRC WA

Post by 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));
   }
}
You're never too old to become younger...

MeteorRain
New poster
Posts: 3
Joined: Sat Mar 18, 2006 7:00 am

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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
Last edited by chunyi81 on Sun Mar 19, 2006 2:49 pm, edited 1 time in total.

Post Reply

Return to “Volume 1 (100-199)”