TweetFollow Us on Twitter

CRC
Volume Number:9
Issue Number:4
Column Tag:Pascal Workshop

CRCs in Pascal

Checking your data when transferring from one computer to another

By Mark R. Drake, Minneapolis, Minnesota

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

About the author

Mark R. Drake is a programmer for Detector Electronics in Minneapolis, Minnesota. His main areas of interest are communications and industrial computer control.

When transferring data from one computer to another via serial devices, the careful application of data integrity checking is required to ensure the validity of the data. In the industrial computer world, data that is transferred from one computer to another may be controlling a large piece of machinery and if the data contains an error and the error is not detected, damage to the machinery and injury to personal may occur.

Several different methods of data error checking are used, but we will cover the one that is used most often in the Macintosh world.

One of the best data error checking methods that can be used is the “Cyclical Redundancy Check” (CRC). Without getting into the mathematical reasons why CRC is good, we will just let stand that it offers a high level of protection. If you want more information on the mathematical properties of CRC generation, your local library should have plenty of information.

You can calculate a CRC check value on a block of bytes by performing a few initializations and then test each bit in each byte to determine if you do one of two possible operations. Refer to Example One. You would pass each byte in the block to the “DoCrcCal” procedure. After you have tested all of the bytes in the block, you will have the CRC check value. As you can see, that method is very slow because you have to test every bit and then do a logical operation to decide which operation to perform. On a Macintosh with a 2400 baud modem, you will not notice the loss of time. With any higher baud rates the lost time is substantial.

Example One
var
 crcCC: longint;

procedure DoCrcCal(theData:longint);
 const
 hiBitMask = $08000;
 polyCCITT = $01021; {CRC-CCITT polynomial}
 polyCRC16 = $0A001; {CRC16 polynomial}
 var
 loop: integer;
 tempdata, crcXor: longint;
begin
 crcCC:= BitXor(BitShift(theData,8),crcCC);
 for loop := 1 to 8 do
 begin
    crcXor := BitAnd(crcCC,hiBitMask);
    if BitTst(@crcXor,16) then
 crcCC:=BitXor(BitShift(crcCC,1),polyCCITT);
    else
     crcCC := BitShift(crcCC,1);
   end;
 crcCC := BitAnd(crcCC,65535);
end;

We can overcome the problem by generating a “CRC lookup table”. Refer to Example Two. We can generate the table and save a great deal of time calculating our CRC check value by doing only two bit shifts per byte compared to eight as required in the first example. Example two is the generation of the lookup table. The generation of the table is calculating a check value in the table for the numbers 0-255. The calculation is the same as the procedure in figure one, but the big difference is that you create this table before you start the transfer.

Table one is a listing of what the table should contain after it is created using the CRC-CCITT polynomial. CRC-CCITT is the polynomial used in Macintosh communications by most vendors.

Example Two
var
 crcTable: array[0..255] of longint;

procedure MakeCRCTable;
 const
 hiBitMask = $08000;
 polyCCITT = $01021; {CRC-CCITT polynomial}
 polyCRC16 = $0A001; {CRC16 polynomial}
 var
 crcCC,crcXor,i,tableCounter: longint;
 loop: byte;
begin
 for tableCounter := 0 to 255 do
 begin
 crcCC := 0;{must be set to zero}
 crcCC:=BitXor(BitShift(tableCounter,8),crcCC);
 for loop := 1 to 8 do
 begin
 crcXor := BitAnd(crcCC,hiBitMask);    if BitTst(@crcXor,16) then
 crcCC:=BitXor(BitShift(crcCC,1),polyCCITT)  
 else
 crcCC := BitShift(crcCC,1);
 end;
 crcTable[tableCounter]:=BitAnd(crcCC,65535);      
 end;
end;

The usage of the lookup table is shown in Example Three. For serial communications I always use a packed array of bytes. The byte that I want to calculate is contained in “byteRec[1]”. I calculate the CRC check value on each byte as the byte is received. The processor can perform thousands of operations while the next byte is coming in the serial controller. So, first I put the data byte into a longint. Then we want to XOR the upper eight bits of the current value of the CRC with the data byte. First shift the current CRC eight bits right and do an XOR with the data byte. This is the value that we are going to use to get the precalculated CRC from the lookup table. Then shift eight bits left and XOR the value from the table with the current value of the CRC. You then have the CRC check value. That’s it. The BitAnd’s are for safety.

Example Three
var
 tempdata,crc,crcCC,temp1,temp2: longint;

crcCC := 0; {must be set to zero}

{when you start to calculate the CRC you must}
{set the crcCC variable to zero}
{it must be set to zero before every new}
{CRC that you calculate}

tempData := byteRec[1];   {the byte to use}
crcCC := BitAnd(BitXor(BitShift(crcCC,8), crcTable[BitAnd(BitXor(BitShift(crcCC,-8), 
tempData),255)]),65535);

{the above broken into separate lines}
tempData := byteRec[1];   {the byte to use}
temp1:=BitShift(crcCC,-8);
temp2 := BitXor(temp1,tempData);
temp2 := BitAnd(temp2,255); {safety}
crc := crcTable[temp2];
temp1 := BitShift(crcCC,8);
temp2 := BitXor(temp1,crc)
crcCC := BitAnd(temp2,65535); {safety}

Testing the speed

The following listing is a program to test the speed of the two methods of CRC calculation. The two procedures that perform the test are called ten times. I have used the Think Pascal profiler to determine the speed. Refer to the Results table. The test was performed on a standard MacPlus. The results of the profiler have been saved to a file in the program.

program Main;

 uses
  Profiler;

 var
  crcTable: array[0..255] of longint;
  crcCC1, crcCC2: longint;
  x: integer;

 procedure DoCrcBitCalc;
  const
   hiBitMask = $08000;
   polyCCITT = $01021;
   polyCRC16 = $0A001;
  var
   loop, i: integer;
   tempdata, crcXor: longint;
 begin
  crcCC2 := 0;
  for i := 0 to 255 do
   begin
    tempData := i;
    crcCC2:=BitXor(BitShift(tempData,8), crcCC2);
    for loop := 1 to 8 do
     begin
      crcXor := BitAnd(crcCC2, hiBitMask);
      if BitTst(@crcXor, 16) then
       crcCC2:=BitXor(BitShift(crcCC2,1), polyCCITT)
      else
       crcCC2 := BitShift(crcCC2, 1);
     end;
    crcCC2 := BitAnd(crcCC2, 65535);
   end;
 end;

 procedure DoTableTest;
  var
   i: integer;
   tempData, crc: longint;
 begin
  crcCC1 := 0;
  for i := 0 to 255 do
   begin
    tempData := i;
    crcCC1 := BitAnd(BitXor(BitShift(crcCC1,8),
      crcTable[BitAnd(BitXor(BitShift(crcCC1,-8),
      tempData),255)]),65535);
   end;
 end;

 procedure MakeCRCTable;
  const
   hiBitMask = $08000;
   polyCCITT = $01021;  {CRC-CCITT polynomial}
   polyCRC16 = $0A001;  {CRC16 polynomial}
  var
   crcCC, crcXor, i, tableCounter: longint;
   loop: byte;
 begin
  for tableCounter := 0 to 255 do
   begin
    crcCC := 0;  {must be set to zero}
  crcCC:=BitXor(BitShift(tableCounter,8),                      
 crcCC);
    for loop := 1 to 8 do
     begin
      crcXor:=BitAnd(crcCC,hiBitMask);
      if BitTst(@crcXor, 16) then
       crcCC:=BitXor(BitShift(crcCC,1),polyCCITT)              
  else
       crcCC := BitShift(crcCC, 1);                      end;
    crcTable[tableCounter]:=BitAnd(crcCC, 65535);
   end;
 end;

begin
 MakeCRCTable;
 for x := 0 to 99 do
  begin
   DoCrcBitCalc;
   DoTableTest;
  end;
 DumpProfileToFile(‘CRCTestFile’);
end.

Results Table

THINK Pascal Procedure Profile

All time is measured in milliseconds and rounded down to the nearest 
millisecond.
Elapsed Time  =   26176
Measured Time =   26111
Total Calls   =      21

Routine Min Max Avg Total % Times

Name Time Time Time Time Time Called

MAKECRCT 2157 2157 2157 2157 8.26 1

DOCRCBIT 2144 2153 2146 21465 82.21 10

DOTABLET 248 250 248 2489 9.53 10

As the test shows, the CRC table lookup method is more than eight times faster than the test every bit method. The correct CRC check value for 0-255 using the CRC-CCITT polynomial is $7E55.

Conclusion

The lookup table method has the speed overhead of creating the table, but this overhead is offset by the amount of data that is transferred or is to be used to calculate the check value. The lookup table method is much easier to work with. The code size and data size is greater with the lookup table method, but I think the speed advantage is so great that the extra words of code and data are put to good use.

Table One
   |  -0- -1-  -2- -3-  |
000: 0000 0000 0000 1021 0000 2042 0000 3063
010: 0000 4084 0000 50A5 0000 60C6 0000 70E7
020: 0000 8108 0000 9129 0000 A14A 0000 B16B
030: 0000 C18C 0000 D1AD 0000 E1CE 0000 F1EF
040: 0000 1231 0000 0210 0000 3273 0000 2252
050: 0000 52B5 0000 4294 0000 72F7 0000 62D6
060: 0000 9339 0000 8318 0000 B37B 0000 A35A
070: 0000 D3BD 0000 C39C 0000 F3FF 0000 E3DE
080: 0000 2462 0000 3443 0000 0420 0000 1401
090: 0000 64E6 0000 74C7 0000 44A4 0000 5485
0A0: 0000 A56A 0000 B54B 0000 8528 0000 9509
0B0: 0000 E5EE 0000 F5CF 0000 C5AC 0000 D58D
0C0: 0000 3653 0000 2672 0000 1611 0000 0630
0D0: 0000 76D7 0000 66F6 0000 5695 0000 46B4
0E0: 0000 B75B 0000 A77A 0000 9719 0000 8738
0F0: 0000 F7DF 0000 E7FE 0000 D79D 0000 C7BC
100: 0000 48C4 0000 58E5 0000 6886 0000 78A7
110: 0000 0840 0000 1861 0000 2802 0000 3823
120: 0000 C9CC 0000 D9ED 0000 E98E 0000 F9AF
130: 0000 8948 0000 9969 0000 A90A 0000 B92B
140: 0000 5AF5 0000 4AD4 0000 7AB7 0000 6A96
150: 0000 lA71 0000 0A50 0000 3A33 0000 2A12
160: 0000 DBFD 0000 CBDC 0000 FBBF 0000 EB9E
170: 0000 9B79 0000 8B58 0000 BB3B 0000 AB1A
180: 0000 6CA6 0000 7C87 0000 4CE4 0000 5CC5
190: 0000 2C22 0000 3C03 0000 0C60 0000 1C41
lA0: 0000 EDAE 0000 FD8F 0000 CDEC 0000 DDCD
lB0: 0000 AD2A 0000 BD0B 0000 8D68 0000 9D49
lC0: 0000 7E97 0000 6EB6 0000 5ED5 0000 4EF4
lD0: 0000 3E13 0000 2E32 0000 1E51 0000 0E70
lE0: 0000 FF9F 0000 EFBE 0000 DFDD 0000 CFFC
lF0: 0000 BFlB 0000 AF3A 0000 9F59 0000 8F78
200: 0000 9188 0000 8lA9 0000 BlCA 0000 A1EB
210: 0000 Dl0C 0000 C12D 0000 F14E 0000 E16F
220: 0000 1080 0000 00A1 0000 30C2 0000 20E3
230: 0000 5004 0000 4025 0000 7046 0000 6067
240: 0000 83B9 0000 9398 0000 A3FB 0000 B3DA
250: 0000 C33D 0000 D31C 0000 E37F 0000 F35E
260: 0000 02Bl 0000 1290 0000 22F3 0000 32D2
270: 0000 4235 0000 5214 0000 6277 0000 7256
280: 0000 B5EA 0000 A5CB 0000 95A8 0000 8589
290: 0000 F56E 0000 E54F 0000 D52C 0000 C50D
2A0: 0000 34E2 0000 24C3 0000 14A0 0000 0481
2B0: 0000 7466 0000 6447 0000 5424 0000 4405
2C0: 0000 A7DB 0000 B7FA 0000 8799 0000 97B8
2D0: 0000 E75F 0000 F77E 0000 C71D 0000 D73C
2E0: 0000 26D3 0000 36F2 0000 0691 0000 16B0
2F0: 0000 6657 0000 7676 0000 4615 0000 5634
300: 0000 D94C 0000 C96D 0000 F90E 0000 E92F
310: 0000 99C8 0000 89E9 0000 B98A 0000 A9AB
320: 0000 5844 0000 4865 0000 7806 0000 6827
330: 0000 18C0 0000 08E1 0000 3882 0000 28A3
340: 0000 CB7D 0000 DB5C 0000 EB3F 0000 FB1E
350: 0000 8BF9 0000 9BD8 0000 ABBB 0000 BB9A
360: 0000 4A75 0000 5A54 0000 6A37 0000 7A16
370: 0000 0AFl 0000 lAD0 0000 2AB3 0000 3A92
380: 0000 FD2E 0000 ED0F 0000 DD6C 0000 CD4D
390: 0000 BDAA 0000 AD8B 0000 9DE8 0000 8DC9
3A0: 0000 7C26 0000 6C07 0000 5C64 0000 4C45
3B0: 0000 3CA2 0000 2C83 0000 1CE0 0000 0CC1
3C0: 0000 EFlF 0000 FF3E 0000 CF5D 0000 DF7C
3D0: 0000 AF9B 0000 BFBA 0000 8FD9 0000 9FF8
3E0: 0000 6E17 0000 7E36 0000 4E55 0000 5E74
3F0: 0000 2E93 0000 3EB2 0000 0EDl 0000 1EFO
   |  -252- -253--254-  -255- |

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.0.3 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
Microsoft Office Preview 15.8 - Popular...
Welcome to the new and modern Microsoft Office for Mac. You will receive regular updates automatically until the official release in the second half of 2015. With the redesigned Ribbon and your... Read more
Yosemite Cache Cleaner 9.0.5 - Clear cac...
Yosemite Cache Cleaner is an award-winning general purpose tool for OS X. YCC makes system maintenance simple with an easy point-and-click interface to many OS X functions. Novice and expert users... Read more
ExpanDrive 4.3.2 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
RapidWeaver 6.0.8 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
Artlantis Studio 5.1.2.7 - 3D rendering...
Artlantis Studio is a unique and ideal tool for performing very high resolution rendering easily and in real time. The new FastRadiosity engine now lets you compute images in radiosity-even in... Read more
MacUpdate Desktop 6.0.5 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
BitTorrent Sync 2.0.82 - Sync files secu...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Google Drive 1.20 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Simon 4.0.3 - Monitor changes and crashe...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more

New Publisher Allstar Games Heads West w...
Allstar Games has announced its first mobile title designed for western audiences, Allstar Heroes. The game will be a massive online battle arena (MOBA) that offers dozens of heroes for you to collect and pit against your opponents. As each hero has... | Read more »
RAD Boarding Review
RAD Boarding Review By Jennifer Allen on March 5th, 2015 Our Rating: :: NEARLY RADUniversal App - Designed for iPhone and iPad RAD Boarding isn’t quite one of the greats, but it has potential.   | Read more »
Presenting the International Mobile Gami...
11th Annual International Mobile Gaming Awards ceremony, hosted by actress Allison Haislip, gathered mobile game developers and publishers from around the world. They chose 13 winners out of the 93 nominations. British studio USTWO won the the Grand... | Read more »
AG Drive Review
AG Drive Review By Tre Lawrence on March 5th, 2015 Our Rating: :: FUTURISTIC STREET RACING.Universal App - Designed for iPhone and iPad Futuristic racing… interstellar style.   | Read more »
GDC 2015 – Nightmare Guardians is an Int...
GDC 2015 – Nightmare Guardians is an Interesting Hybrid of MOBA and Lane Defense Posted by Rob Rich on March 5th, 2015 [ permalink ] I have to say that lane defense (i.e. | Read more »
Overkill 3 Review
Overkill 3 Review By Tre Lawrence on March 5th, 2015 Our Rating: :: WHO'S NEXT?Universal App - Designed for iPhone and iPad Cover system gameplay in the third-person.   Developer: Craneballs Price: Free Version Reviewed: 1.1.6... | Read more »
Warner Bros. Interactive Entertainment A...
Warner Bros. has some exciting games coming down the pipe! | Read more »
GDC 2015 – Star Trek Timelines will Prob...
GDC 2015 – Star Trek Timelines will Probably Make Your Inner Trekkie Squeal With Glee Posted by Rob Rich on March 4th, 2015 [ permalink ] Any popular fictional universe has its fair share of fan fiction – where belo | Read more »
Protect Yourself from an Onslaught of Ca...
Surprise Attack Games has announced a Cat-astrophic new physics puzzler called Fort Meow! In the game, a young girl named Nia finds her grandfather’s journal which triggers an all mighty feline attack! Why do the cats want the journal? Who knows,... | Read more »
GDC 2015 – Jelly Reef will be Game Oven’...
GDC 2015 – Jelly Reef will be Game Oven’s Last Hurrah, and it Seems like a Good Note to Go Out on Posted by Rob Rich on March 4th, 2015 [ permalink ] It’s sad knowing that Game Oven ( | Read more »

Price Scanner via MacPrices.net

Roundup of MacBook Air sale prices, models up...
B&H Photo has MacBook Airs on sale for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 100 off MSRP - 11″ 256GB MacBook Air: $999 $100... Read more
New Firstrade Mobile App Enables On-The-Go Tr...
Firstrade Securities Inc. has announced its new mobile app, which gives investors immediate access to the company’s trading platform on all mobile devices. The app was developed in-house and was... Read more
Sonnet Introduces USB 3.0 + eSATA Thunderbolt...
Sonnet has announced the launch of its new USB 3.0 + eSATA Thunderbolt Adapter for easy connectivity to USB 3.0 devices and eSATA storage, and USB 3.0 + Gigabit Ethernet Thunderbolt Adapter for easy... Read more
Apple restocks refurbished 27-inch 5K iMacs f...
The Apple Store has restocked Apple Certified Refurbished 27″ 3.5GHz 5K iMacs for $2119 including free shipping. Their price is $380 off the cost of new models, and it’s the lowest price available... Read more
Free Clean Reader Mobile App Hides Swear Word...
The new Clean Reader app, now available in the Apple App Store and Google Play, delivers the opportunity of reading any book without being exposed to profanity. By selecting how clean they want their... Read more
Kinsa Launches “Groups” App to Monitor Illnes...
Kinsa, makers of the first FDA approved app-enabled smartphone thermometer thst won the 2013 Cleveland Clinic Medical Innovation Grand Prize and recently appeared in Apple’s “Parenthood” TV... Read more
iPad: A More Positive Outlook – The ‘Book Mys...
It’s good to hear someone saying positive things about the iPad. I’ve been trying to bend my mind around how Apple’s tablet could have gone from zero to bestselling personal computing device on the... Read more
Mac Pros on sale for up to $279 off MSRP
Amazon has Mac Pros in stock and on sale for up to $279 off MSRP. Shipping is free: - 4-Core Mac Pro: $2725.87, $273 off MSRP (9%) - 6-Core Mac Pro: $3719.99, $279 off MSRP (7%) Read more
Sale! 13-inch Retina MacBook Pros for up to $...
B&H Photo has 13″ Retina MacBook Pros on sale for up to $205 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1219.99 save $80 - 13″ 2.... Read more
Another Tranche Of IBM MobileFirst For iOS Ap...
IBM has announced the next expansion phase for  its IBM MobileFirst for iOS portfolio, with a troika of new apps to address key priorities for the Banking and Financial Services, Airline and Retail... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.