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

Apple Security Update 2015-005 - For OS...
Apple Security Update 2015-005 is recommended for all users and improves the security of OS X. For detailed information about the security content of this update, please visit: http://support.apple.... Read more
Apple HP Printer Drivers 3.1 - For OS X...
Apple HP Printer Drivers includes the latest HP printing and scanning software for OS X Lion or later. For information about supported printer models, see this page. Version 3.1: The latest printing... Read more
Epson Printer Drivers 3.1 - For OS X 10....
Epson Printer Drivers installs the latest software for your EPSON printer or scanner for OS X Yosemite, OS X Mavericks, OS X Mountain Lion, and OS X Lion. For more information about printing and... Read more
Xcode 6.4 - Integrated development envir...
Xcode provides everything developers need to create great applications for Mac, iPhone, and iPad. Xcode brings user interface design, coding, testing, and debugging into a united workflow. The Xcode... Read more
OS X Yosemite 10.10.4 - Apple's lat...
OS X Yosemite is Apple's newest operating system for Mac. An elegant design that feels entirely fresh, yet inherently familiar. The apps you use every day, enhanced with new features. And a... Read more
Dash 3.0.2 - Instant search and offline...
Dash is an API Documentation Browser and Code Snippet Manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
FontExplorer X Pro 5.0 - Font management...
FontExplorer X Pro is optimized for professional use; it's the solution that gives you the power you need to manage all your fonts. Now you can more easily manage, activate and organize your... Read more
Typinator 6.6 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
Arq 4.12.1 - Online backup to Google Dri...
Arq is super-easy online backup for the Mac. Back up to your own Google Drive storage (15GB free storage), your own Amazon Glacier ($.01/GB per month storage) or S3, or any SFTP server. Arq backs up... Read more
Gutenprint 5.2.11-pre1 - Quality drivers...
Gutenprint is a suite of printer drivers that may be used with most common UNIX print spooling systems, including CUPS, lpr, LPRng, or others. Gutenprint currently supports over 2000 printer models.... Read more

Vector 2 is Officially a Thing and it...
Vector is a pretty cool parkour-driven runner that's gotten a pretty decent following since it first came out - although personally I think more people could stand to show it some love. Anyway, Nekki has announced that a sequel isofficially on its... | Read more »
This Week at 148Apps:June 22-26, 2015
June's Summer Journey Continues With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice,... | Read more »
LEGO® Minifigures Online (Games)
LEGO® Minifigures Online 1.0.1 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: | Read more »
World of Tanks Blitz celebrates its firs...
Today marks the first anniversary of the launch of World of Tanks Blitz, the mobile version of the PC tank battler, World of Tanks. World of Tanks Blitz launched on iOS and Android on June 26th last year and to celebrate, Wargaming is giving all... | Read more »
Heroes and Castles 2 Has its Own Standal...
Heroes and Castles 2 is a third-person castle defense game from the same team behind Block Fortress and Bug Heroes. It's cool, it's fun, and now it has its very own free version. [Read more] | Read more »
Formula Cartoon All-Stars Lets You Race...
Ever want to pit your favorite characters from shows like Steven Universe, Adventure Time, and Regular Show against each other in a not quite death race? Well once upon a time you could, but Formula All Stars Touch N' Go doesn't exist anymore. Hope... | Read more »
Retype - Typography Photo Editor (Photo...
Retype - Typography Photo Editor 1.0 Device: iOS Universal Category: Photography Price: $2.99, Version: 1.0 (iTunes) Description: Retype is built out of passion for great typography and it's all about adding text to photo with style... | Read more »
Hungry Shark Evolution Celebrates Shark...
Shark Week is almost here, as is Independence Day, so naturally Hungry Shark Evolution is going to get in on the action. Yes, even the fireworks. [Read more] | Read more »
The New Trivia Crack Will Feature a Musi...
It's official: iHeartMedia (you may know them from iHeartRadio) will be in charge of providing music-related questions for Trivia Crack's upcoming sequel. Also Trivia Crack is getting a sequel. [Read more] | Read more »
Toca Life: City (Education)
Toca Life: City 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: Welcome to Toca Life: City, a metropolis filled with everyday fun! Customize characters, explore exciting locations and... | Read more »

Price Scanner via MacPrices.net

OtterBox Releases New Symmetry Series Metalli...
Otterbox’s new Symmetry Series of smartphone cases flaunts the best of both both street style and street smarts with their new metallic finishes and trusted OtterBox protection for iPhone 6 and... Read more
MacBook Airs on sale for up to $75 off MSRP
Save up to $75 on the purchase of a new 2015 13″ or 11″ 1.6GHz MacBook Air at the following resellers. Shipping is free with each model: 11" 128GB MSRP $899 11" 256GB... Read more
Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store has Apple Certified Refurbished Mac Pros available for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Mac Pros on sale for up to $260 off MSRP
B&H Photo has Mac Pros on sale for up to $260 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2799, $200 off MSRP - 3.5GHz 6-core Mac Pro: $3719.99... Read more
Save up to $400 on 2014 15-inch Retina MacBoo...
B&H Photo has previous-generation 2014 15″ Retina MacBook Pros on sale for up to $400 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has new 2015 15″ Retina MacBook Pros on sale for up to $125 off MSRP including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1899.99 $100 off - 15″ 2.5GHz... Read more
College Student Deals: Additional $100 off Ma...
Take an additional $100 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through July 11, 2015. Anyone with a valid .EDU email address can take advantage... Read more
Apple refurbished Time Capsules available for...
The Apple Store has certified refurbished Time Capsules available for $100 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $199, $100... Read more
Newsweek Launches iPhone App
The venerable weekly news magazine Newsweek, owned by IBT Media, has announced the launch of its first iPhone app. The new app is available through Apple’s App Store and will allow consumers to read... Read more

Jobs Board

*Apple* TV Live Streaming Frameworks Test En...
**Job Summary** Work and contribute towards the engineering of Apple 's state-of-the-art products involving video, audio, and graphics in Interactive Media Group (IMG) at Read more
Project Manager, WW *Apple* Fulfillment Ope...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
Senior Data Scientist, *Apple* Retail - Onl...
**Job Summary** Apple Retail - Online sells Apple products to customers around the world. In addition to selling Apple products with unique services such as iPad Read more
*Apple* Music Producer - Apple (United State...
**Job Summary** Apple Music seeks a Producer to help shepherd some of the most important content and editorial initiatives within the music app, with a particular focus Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.