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

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Tue Jun 10, 2003 10:28 pm

I think you should use bit-wise operations instead of time-consuming multiplication. For example, instead of
[cpp]
a = a*256;
[/cpp]
you should use

[cpp]
a = a<<8;
[/cpp]

and instead of
[cpp]
a = a*256*256;
[/cpp]
you should use

[cpp]
a = a<<16;
[/cpp]

that should speed up your code.
this is how your code should look like

[cpp]
#include<iostream>
#include<string>
using namespace std;

string output(int a){
string result,no="0123456789ABCDEF";
for(int j=1;j<=4;a>>=4,j++){
int i=a%16;
result=no+result;
}
return result.substr(0,2)+" "+result.substr(2);
}

int main(){
string buffer;
int i;
while(true){
string buffer;
char bu;
while(cin.get(bu)){
if(bu=='\n')
break;
buffer=buffer+bu;
}
if(buffer[0]=='#')
return 0;
int length=buffer.length(),base=0,checksum;
if(length==0){
cout<<"00 00"<<endl;
continue;
}
for(i=0;i<length;i++)
base=(base<<8+buffer)%34943;
base=(base<<16)%34943;
checksum= (base==0?base:(34943-base));
cout<<output(checksum)<<endl;
}
return 0;
}[/cpp]

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Tue Jun 10, 2003 10:40 pm

strange. I tried your code, but it is still giving me time limit exceeded. I think you should try do do something about output function. It seems to be a bit-time consuming.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Wed Jun 11, 2003 12:33 am

anyway, this code doesn't give that time limit error, but it still gives WA. I think our problem is in this place
[cpp]
while(cin.get(bu)){
if(bu=='\n')
break;
buffer=buffer+bu;
}

[/cpp]
have a look at how I've done it. I don't know what you are waiting for in the above while loop. I think your program gets stuck at that place.

[cpp]
#include<fstream>
#include<iostream>
#include<string>
#include<stdio.h>

using namespace std;

int main(){
string buffer;
int i;

int nLowerByteCRC;
int nHigherByteCRC;
char bu;
char chStr[1024];

int length,base,checksum;
while(1)
{
memset(chStr,0,1024);
cin.getline(chStr,1024);
buffer = chStr;

if(buffer[0]=='#')
return 0;

length=buffer.length();
base=0;

if(length==0){
cout<<"00 00"<<endl;
continue;
}
for(i=0;i<length;i++)
base=(base<< 8 )|(buffer)%34943;
base=(base<<16)%34943;
checksum= (base==0?base:(34943-base));

nHigherByteCRC = checksum >>8;
nLowerByteCRC = checksum & (int)(0x00FF);
printf("%02X %02X\n",nHigherByteCRC,nLowerByteCRC);

}
return 0;
} [/cpp][/cpp][cpp][/cpp]

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Wed Jun 11, 2003 11:55 pm

come on, Guys! I've been waiting for an answer for ages. :-?

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

Post by boatfish » Thu Jun 12, 2003 9:13 am

Thanks to all.
I have solved the problem:)

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Thu Jun 12, 2003 10:00 am

boatfish wrote:Thanks to all.
I have solved the problem:)
mmm. could you please email me your code, because I don't know why it gives me this rubbish WA.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Thu Jun 12, 2003 10:30 am

guys, please! help. :cry:

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jun 12, 2003 12:02 pm

Input:

Code: Select all

RFC: 793
#
Your output:

Code: Select all

10A 21

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Thu Jun 12, 2003 12:07 pm

Ivan Golubev wrote:Input:

Code: Select all

RFC: 793
#
Your output:

Code: Select all

10A 21
thanks. can anybody tell me why is it happening? actually, when I change long to unsigned it gives correct results.
I am just wondering why is it happening.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Thu Jun 12, 2003 12:16 pm

I can't believe I made this rubbish mistake. it was all because of this line
[cpp]
nHigherByteCRC = CRC>>8;
[/cpp]
it should be this
[cpp]
nHigherByteCRC = (int)(0x00ff) & (CRC>>8 );
[/cpp]
unbelievable. :evil:
thanks, Ваня.
Last edited by Experimenter on Thu Jun 12, 2003 4:18 pm, edited 1 time in total.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Thu Jun 12, 2003 12:17 pm

Besides, can anybody tell me why am I getting presentation error now?
the output is below.

thanks.[cpp]
#include <fstream>
#include <string>
#include <iostream>
#include <iomanip>
#include <memory>
#include <stdio.h>

using namespace std;

typedef unsigned char BOOL;

const BOOL FALSE = 0;
const BOOL TRUE = 1;

int main();
long Reminder(char *chMessage,int nDWLen,long lnGenerator);

int main()
{

const long lnGenerator = 34943;
const int nAddLetters = 4;
const int nDataLen = 1024 + nAddLetters + 2;// 1024- for the data,
// 2 - for Redundancy Error
// 4 - for correcting the data length (make even)


long r;
long CRC;
int tAdd,tBegin,rem;
int nLowerByteCRC;
int nHigherByteCRC;
int num = 0;

char chData[nDataLen];
char *chMessage = NULL;
BOOL fl = TRUE;
int nReadLen = 0;
int nMessageLen= 0;

//ifstream fin ("input.txt");
//ofstream fout("output.txt");

while(fl)
{

memset((void *)chData,0,(size_t)(nDataLen*sizeof(chData[0])));
//fin.getline(&chData[nAddLetters],nDataLen);
cin.getline(&chData[nAddLetters],nDataLen,'\n');
nReadLen = strlen(&chData[nAddLetters]);


if('#' == chData [nAddLetters])
{
fl = FALSE;
}
else
{
rem = (nReadLen + 2)% 4;
tAdd = (!rem) ? 0 : (4 - rem); // number of letters to add
tBegin = (!rem) ? 4 : rem ; // where the message will start
nMessageLen = nReadLen + 2 + tAdd ; // message length
chMessage = (char *)&chData[tBegin];

// calculate CRC

r = Reminder(chMessage,(nMessageLen>>2),lnGenerator);
CRC = (0 == r) ? 0 : (lnGenerator - r);

nHigherByteCRC = (int)(0x00FF) & (CRC>>8 );
nLowerByteCRC = CRC & (int)(0x00FF);
//printf("%02X %02X \n",nHigherByteCRC,nLowerByteCRC);
cout.fill('0');
//fout.setf(ios_base::hex,ios_base::showbase);
cout<<hex<<setw(2)<<nHigherByteCRC<<" ";
cout<<hex<<setw(2)<<nLowerByteCRC <<endl;//<<dec<<++num<<endl;

}


}


//fin.close();
//fout.close();
return (0);
}

long Reminder(char *chMessage,int nDWLen,long lnGenerator)
{
long r;
long t;
int i;

const int nIter = 2*nDWLen - 1;
r = (int)chMessage[0];
r<<= 8;
r |= chMessage[1];


for(i = 1; i <= nIter; i++)
{
t = r;
t<<= 16;
t |= (((int)chMessage[i*2])<<8 ) | ((int)chMessage[i*2 + 1]);
r = t % lnGenerator;
}

return (long)r;
}
[/cpp]

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

Post by ayaw » Tue Jun 17, 2003 11:22 am

i also got WA, anything wrong??

here is it :

Code: Select all

#include <stdio.h>
#include <string.h>
#define LONG unsigned long
#define CRC_V 34943

LONG CRC(char *word) {
      LONG i,cr=0, get;
      for(i=strlen(word)%2==1?-1:0;word[i];i+=2) {
            get = cr * 0x10000;
            if(i!=-1) get += (LONG) word[i] * 0x100;
            get += word[i+1];
            cr = get%CRC_V;
      }
      return ( CRC_V - ((cr*0x10000)%CRC_V ) ) % CRC_V;
}

main() {
      char word[2028];
      while(1) {
            gets(word);
            if(word[0]=='#') return 0;
            printf("%02lX %02lX\n",CRC(word)/0x100,CRC(word)%0x100);
      }
}
peace...

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Tue Jun 17, 2003 11:26 am

try to output your answers in the file, I mean for all the strings length from 0 to 1024 and compare them with the output of my program as I got AC, though with presenation error.
That's what I did and really helped.
it would be great if you replied this post. really.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

128 (CRC) Weird Java / C++ discrepancy

Post by xbeanx » Tue Sep 02, 2003 4:07 am

Hi guys. I did problem number 128 in JAVA, only to get a TLE (as is common with java).

Anyway, so I converted my program directly to C++ code, only to find it doesn't work the same. I think you'll agree the conversion is quite straight forward. Please, if someone can make a suggestion I'd be greatful.

Both programs are below, as well as the offending input....

[java]import java.io.IOException;

class Main {
static final long generator = 34943;

public static void main(String[] args) {
String input;
while((input = readLine(2048)) != null) {
if(input.length() == 0) {
System.out.println("00 00");
continue;
}

if(input.charAt(0) == '#') System.exit(0);

long crc = 0;
for(int i = 0; i < input.length(); i++)
crc = ((crc << 8) + input.charAt(i)) % generator;
crc = (crc << 16) % generator;
if(crc != 0) crc = generator - crc;
long hiByte = crc >> 8;
long loByte = crc - (hiByte << 8);

String h = Long.toHexString(hiByte).toUpperCase();
String l = Long.toHexString(loByte).toUpperCase();
System.out.println((h.length() < 2 ? "0" : "") + h + " " +
(l.length() < 2 ? "0" : "") + l);
}
}

static String readLine(int maxLg) {
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
while(lg < maxLg) {
try{car = System.in.read();}
catch(IOException e) {return null;}
if(car<0 || car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg).trim();
}
}[/java]

[cpp]#include <iostream>
#include <string>

#define MAX_INPUT 1024
#define GENERATOR 34943

using namespace std;

int main() {
char in[MAX_INPUT];
while(cin.getline(in, MAX_INPUT, '\n')) {
int len = strlen(in);

if(in[len-1] == '\r') len--;

if(len == 0) {
cout << "00 00" << endl;
continue;
}

if(in[0] == '#') return 0;

long crc = 0;
for(int i = 0; i < len; i++)
crc = ((crc << 8) + in) % GENERATOR;
crc = (crc << 16) % GENERATOR;
if(crc) crc = GENERATOR - crc;

long hiByte = crc >> 8;
long loByte = crc - (hiByte << 8);

cout.fill('0');
cout.width(2);
cout.setf(ios::uppercase);
cout << hex << hiByte << " " << loByte << endl;
}
return 0;
}[/cpp]

And these programs seem to give identical output for all input sets except the following:

Code: Select all

***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
***********************************************************
*******************
That's 1023 stars, FYI (just remove the returns so its all on one line). Can anyone see why both programs give different output? Am I overflowing anywhere?

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Tue Sep 02, 2003 4:53 am

Oops. I figured out where the problem was... It turns out that, although my JAVA program works fine using simple ints (which is what I used first), the C++ program must use unsigned longs.

Anyway, problem solved once again! :)

PS, there's a deliberate bug inserted in my program so no one can submit it. ;-)

Post Reply

Return to “Volume 1 (100-199)”