The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Tuesday, October 14, 2014

It makes you sound as if you are talking in a fake German accent

I'm sitting in the Ft. Lauderdale Office of the Corporation, using the Lookout email client when I receive the following:

Vishing is a socially engineered technique for stealing information or money from people using the telephone network. The term comes from combining “voice” with “phishing,” which are online scams that get people to give up personal or sensitive information about The Corporation. This may include impersonating another employee of the Corporation, your bank, law enforcement agencies or any government related organization via voice email, VoIP (voice over IP), or landline or cellular telephone.

Vishing?

Vishing?

Really?

Oh, I guess it's a thing now.

Sigh.

We already have a term for this—“phishing!” Or perhaps “social engineering?” How about “hacking” if you want to go old school 80s style terminology?

Good lord …

Sunday, October 26, 2014

The Painless Guide to CRC isn't quite painless

So there's this “A Painless Guide to CRC Error Detection Algorithms,” which apparently tells you everything you wanted to know about CRCs, but were afraid to ask (or didn't really want to ask). The concept itself seems to be easy—a CRC is just the remainder of a particular type of division. The numerator is the data (treated as one long number) and the demoninator the “polynomial” of the CRC (even though it's a value, the specification for a given CRC is a polynomial equation—go figure). The steps of the algorithm are very simple:

1. Load the remainder with zero bits.
2. Augment the message by appending zero bits (equal to the size of the remainder) to the end of it.
3. While (more message bits)
   1. Shift the remainder left by one bit, reading the next bit of the augmented message into bit position 0 of the remainder.
   2. If a 1 bit popped out of the remainder during the previous step, XOR the result with the polynomial
4. We now have the remainder.

The size of the remainder is the size of our CRC—16 for a 16-bit CRC, 32 for a 32-bit CRC, etc. And from that description, the code pretty much follows:

/**********************************************************
* Straightforward CRC implementation 
* Section 8 of the Guide
***********************************************************/

uint32_t crcsim(uint32_t crc,const uint8_t *p,size_t size)
{
  size_t   i;  
  int      c;  
  int      xor;

  while(size--)
  {
    c = *p++;
    for (i = 0 ; i < 8 ; i++)
    {
      xor = crc & 0x80000000uL;  /* flag if we need to xor the polynomial */
      crc = crc << 1;            /* shift the crc register */   
      crc |= (c & 0x80) ? 1 : 0; /* and shift in the data bit */
 
      if (xor)
        crc ^= 0x04C11DB7uL;
 
      c = c << 1; /* shift data bit */
    }
  }
  
  return crc;
}

Although, this is the rare case where it's easier to write it in assembly that it is in C, since we have access to the carry bit when shifting, which makes it easier to check:

crc32a          push    ebp		; boiler plate code for any
                mov     ebp,esp		; C callable code
                push    ebx
                push    esi
                push    edi

                mov     edx,[ebp + 8]   ; load passed in CRC
                mov     esi,[ebp + 12]  ; ptr to data
                mov     ecx,[ebp + 16]  ; count of data
                mov     edi,0x04C11DB7  ; CRC polynomial

.main           lodsb                   ; read next data byte
                mov     bl,8            ; # of bits to go through

.10             shl     al,1            ; shift data bit into poly register
                rcl     edx,1           ; shift high bit out of poly register
                jnc     .15             ; if it wasn't set, skip
                xor     edx,edi         ; xoring the CRC polynomial

.15             dec     bl              ; more bits?
                jnz     .10             ; if so, keep going
                loop    .main           ; do next byte

                mov     eax,edx         ; return CRC
                pop     edi             ; save pushed registers
                pop     esi
                pop     ebx
                pop     ebp
                ret

(Note: the core of the algorithm in assembly is four instructions---the C compiler didn't do quite as good a job from the six lines of C comprising the core of the algorithm---it's about six times the object code.)

What is not shown in the code above (either version) is the agumentation step of adding additional 0-bits to the message—that's left up to the caller of these routines.

Both of these routines give the same result. Other implementations I did based upon the Guide also give the same results. And they're consistent with the results of the reference code given in the Guide.

/*******************************************************************
* Table implementation
* Section 9 of the Guide
* Requires trailing zero bits.
********************************************************************/

const uint32_t crctable[256] = { ... };

uint32_t crc32z(uint32_t crc,const uint8_t *p,size_t size)
{
  while(size--)
    crc = ((crc << 8) | *p++) ^ crctable[crc >> 24];

  crc = (crc << 8) ^ crctable[crc >> 24];
  crc = (crc << 8) ^ crctable[crc >> 24];
  crc = (crc << 8) ^ crctable[crc >> 24];
  crc = (crc << 8) ^ crctable[crc >> 24];
  return crc;  
} 

/*****************************************************************
* Table implementation part deux---improved
* Section 10 of the Guide
* Does not need trailing zero bits.
******************************************************************/

uint32_t crc32c(uint32_t crc,const uint8_t *p,size_t size)
{
  while(size--)
    crc = (crc << 8) ^ crctable[ (crc >> 24) ^ *p++]; 
      
  return crc; 
}

/*****************************************************************
* Parameterized Model, from code given in the Guide
* Section 15 of the Guide
*
* This is a reference implementation provided by the Guide to be
* used for testing various CRC implementations.
******************************************************************/

uint32_t crcmod(uint32_t crc,const uint8_t *p,size_t size)
{ 
  cm_t ctx;  
 
  ctx.cm_width = 32;
  ctx.cm_poly  = 0x04C11DB7uL;
  ctx.cm_init  = crc;
  ctx.cm_refin = false;
  ctx.cm_refot = false;
  ctx.cm_xorot = 0;
  
  cm_ini(&ctx);
  cm_blk(&ctx,(p_ubyte_)p,(ulong)size);
  return (uint32_t)cm_crc(&ctx);
}

CRC of “123456789” using different implementations

Implementation	CRC result
crcsim()	89A1897F
crc32z()	89A1897F
crc32c()	89A1897F
crcmod()	89A1897F

So far so good. But that isn't the result from the standard CRC-32 implementation, which is used by Ethernet, ZIP, gzip, PNG and a few other standards. No, CRC-32 uses what the Guide calls a “reflected” table mode, which came about because of hardware CRC-implementations start with the least significant bit of the byte; these algorithms start with the most significant bit of the byte.

Okay, so the bits are fed in backwards. That can be compensated for. Also, the standard CRC-32 algorithm mandates that the initial value of the remainder is all one bits, not zero bits. Easy to fix. And that the final remainder is to be exclusived-or'ed with all ones. Again, easy to do.

It all seems pretty straightforward. And while the Guide only goes over a table inplementation of the “reflected” mode, it seems like it would be straightforward (excuse the pun) to do reflected versions of all the implementations done so far.

And since the zlib library uses the CRC-32, we can link that in as a baseline to compare results.

So, with that out of the way, the code:

/**********************************************************
* Straightforward CRC implementation, using reflected bytes
* based on Section 9 of the Guide
***********************************************************/

uint32_t crcsimr(uint32_t crc,const uint8_t *p,size_t size)
{
  size_t   i;
  int      c;
  int      xor;
  
  crc = ~crc;
  while(size--)
  {
    c = *p++;
    for (i = 0 ; i < 8 ; i++)
    {
      xor = crc & 0x80000000uL;
      crc = crc << 1;
      crc |= (c & 0x01) ? 1 : 0;
      
      if (xor)
        crc ^= 0x04C11DB7uL;
 
      c = c >> 1;
    }
  }
  
  return crc;
}

/*******************************************************************
* Table implementation, using a reflected table
* based on Section 9 of the Guide
********************************************************************/

const uint32_t crctabler[256] = { ... };

uint32_t crc32rz(uint32_t crc,const uint8_t *p,size_t size)
{
  crc = ~crc;
  
  while(size--)
    crc = ((crc >> 8) | *p++) ^ crctabler[ crc & 0xFF ];

  crc = (crc >> 8) ^ crctabler[ crc & 0xFF ];
  crc = (crc >> 8) ^ crctabler[ crc & 0xFF ];
  crc = (crc >> 8) ^ crctabler[ crc & 0xFF ];
  crc = (crc >> 8) ^ crctabler[ crc & 0xFF ];

  return ~crc;
}

/*****************************************************************
* Table implementation part deux---improved using reflected table
* based on Section 10 of the Guide
******************************************************************/

uint32_t crc32r(uint32_t crc,const uint8_t *p,size_t size)
{
  crc = ~crc;
  
  while(size--)
    crc = (crc >> 8) ^ crctabler[ (crc & 0xFF) ^ *p++];
 
  return ~crc;
}

/*****************************************************************
* Parameterized Model, from code given in the Guide
* Section 15 of the Guide
*
* This is a reference implementation provided by the Guide to be
* used for testing various CRC implementations.
******************************************************************/

uint32_t crcmodr(uint32_t crc,const uint8_t *p,size_t size)
{
  cm_t ctx;

  ctx.cm_width = 32;
  ctx.cm_poly  = 0x04C11DB7uL;
  ctx.cm_init  = ~crc;
  ctx.cm_refin = true;
  ctx.cm_refot = true;
  ctx.cm_xorot = ~0;
  
  cm_ini(&ctx);
  cm_blk(&ctx,(p_ubyte_)p,(ulong)size);
  return (uint32_t)cm_crc(&ctx);
}

And the results:

CRC of “123456789” using different implemenations, reflected

Implementation	CRC result
crcsimr()	AF296EBB
crc32rz()	717C74D2
crc32r()	CBF43926
crcmodr()	CBF43926
zlib.crc32()	CBF43926

… um … that was rather unexpected.

I didn't think the code I wrote for reflected CRCs was that unreasonable based upon the information in the Guide, but I guess I was wrong for some of them.

Oh, and getting back to the non-reflected code—I didn't initialize the results properly, nor did I exclusive-or the results. Hopefully, I'll get CBF43926 when I do that.

CRC of “123456789” using different implementations, non-reflected with proper initialization

Implementation	CRC result
crcsim()	C8C3A78F
crc32z()	C8C3A78F
crc32c()	FC891918
crcmod()	FC891918

Okay, now I'm horribly confused. There appears to be some missing information in “A Painless Guide to CRC Error Detection Algorithms.” The GNU Radio implementation of CRC-32 uses the non-reflective table implementation, and when I called that, I got back FC891918, so it's consistent with at least two of the CRC-32 non-reflected implementations. But I'm concerned that the routines that require additional zero bits aren't the same in this case. There has to be some subtle difference between the two in this case that I don't see, and isn't mentioned in the Guide at all.

I did find yet another comprehensive implemenation of CRCs—Danjel McGougan's universal_crc, and every version of the non-reflected CRC-32 it generated (it generates either bit-oriented code, or several table-driven implementations based on tradeoffs betweeen speed and memory usage) returned FC891918 (even it's own bit-oriented version, which isn't the same as the one described in the Guide).

Another thing I noticed by looking deeply into the abyss that is CRC, is that my first implementation of CRC-32 is flawed—I don't exclusive-or the results with all ones at the end. I suspect that the code I based mine on didn't bother with the exclusive-or when returning the CRC, but instead did that elsewhere in the codebase. It's not a bug per se, but according to Numerical Recipes in C:

Second, one can add (XOR) any M-bit constant K to the CRC before it is transmitted … This has the advantage of detecting another kind of erorr that the CRC would otherwise not find: deletion of an initial 1 bit in the message with spurious insertion of a 1 bit at the end of the block.

The result is that there's a type of corruption that I won't catch. This code was the basis for the CRC implementation in a few programs at work (oops) but again, I don't think it's an outright show-stopping bug.

At some point, I may go through some of this on paper, one bit at a time, to see what's going on math-wise with the reflected and non-reflected table implementations with non-0 initial values.

Tuesday, October 28, 2014

Brevard III: Season of the Leaf

Ah, nothing like visiting Transylvania during Hallowe'en. Bat country. Gotta love it.

This is our third attempt at visiting Brevard, NC to see the autumn colors. Our first attempt was about two weeks early. The second attempt was about a week late. Hopefully, this time we've timed it right.

The problem with the autumn colors is that they are very dependent upon the weather leading up to Peak Leaf Season. It also depends on how north you are and how high up you are. But I picked this week, and hopefully, it'll be just right.

We left early this morning for the twelve hour drive to Brevard. The only downside to the entire trip was lunch at the Western Sizzler just outside Savannah, Georgia. I ordered a cheeseburger medium rare, not steak tartare au fromage on a bun. Bunny's food was seriously underseasoned. Even the salt was underseasoned. Not a pleasant experience.

We finally arrived at our destination, The Red House Inn. Previously, we've stayed at The Inn at Brevard (on the opposite side of town) but this time I felt it was time to shake things up and try a new place. The Inn At Brevard gives off a definite 1900 period vibe, which is not a bad thing, but The Red House Inn (built in 1851) is a bit more modern. The owners welcomed us and when we told them the reason for our visit, they did say they felt that Brevard was just breaking Peak Leaf Season. Perfect timing! Woot!

We were then shown to our suite I rented. It's about half the second floor, with its own hallway, bedroom, bathroom, living room and private porch. It is certainly worth its price. We dumped our bags, and headed out for dinner.

---

A little bluegrass, a lot of food

The Red House Inn is just a few blocks from downtown Brevard, so Bunny and I decided to walk to dinnner. Our first choice of venue was The Square Root, as it has become a tradition to eat there for our first dinner. Unfortunately, they now close on Tuesdays. The owners of the Red House Inn then recommended Jamie's, a new Creole restaurant that opened a little over a week ago in downtown Brevard.

So Bunny and I walk. Along the way we pass Celestrial Mountain Music, a music and musical instrument store where there were a dozen musicians sitting in a circle playing bluegrass music.

They saw us peering in the window; the bass player leapt across the store and into the street, welcoming us to just listen in as they played. Despite wanting to get to dinner before the sidewalks were rolled up at 9:00 PM we did stay for one musical number before bidding adéu to continue our journey to Jamie's.

It's a popular restaurant and we had to wait a few minutes for a table to open up.

Bunny ordered a shrimp and corn chowder that was quite good. The lump crab salad appetizer was okay (but then again, it's hard to match the crab from Capp's Place). I had the rib-eye steak (an overly generous portion) with mushrooms and grilled corn, which was one of the better rib-eyes I've had. Bunny ordered the French cut chicken with tabouleh and winter vegetables. While her chicken was one of the moistest pieces of white meat (it was expertly cooked) the taste was … there. It wasn't much to write home about. The winter vegetables were a bit underdone but the tabouleh was delicious.

For desert, we ordered the beignnets. While I found them quite good (very light, not overly sweet) Bunny found they didn't quite quench her desire for fried dough.

Over all, we were glad to try the restaurant, but I don't think we'll be making it a regular destination.

Wednesday, October 29, 2014

Locks, stalks, and two near accidents

I had put it off as long as I could, but there was nothing more I could do to delay the inenvitable. Pulling me along by the ear, Bunny lead me into the local barber shop.

After the indignity of having my locks shorn, Buny decided to head to the local grocery store to pick up a few essentials. The local grocery store in this part of the country is Ingles, a store the size of Wally World but with the charm of Publix. No wonder Publix hasn't made it this far north. The Ingles had miles of shelves. There was an olive bar a mile long. We live in Boca Raton and do we rate olive bars in our grocery stores? Nay! Nay, I say! How does Brevard, a small town in rural North Carolina, rate an olive bar? And freshly made locally sourced Mozzarella?

But I digress! Bunny got the essentials she so dearly wanted: hot chocolate and fresh flowers for the room.

---

I must now talk about traffic.

Unlike South Florida, there aren't many thoroughfares in town—in fact, there's only one—Broad Street (also known as US-64, US-276 and Asheville Highway, but unlike Orlando, it's clearly marked at all times). And that's practically the only street with traffic lights. Sure, Main Street (which crosses Broad Street) has a few lights, but the majority of traffic lights are along Broad Street. The rest of the roads in Brevard are primarily two lane roads with a plethora of stop signs.

And the traffic isn't that heavy, even at rush hour.

Okay, given that there are around 33,000 people in the county (compare to nearly 90,000 just in Boca Raton proper) there just isn't much heavy traffic (unlike Alamo, Nevada). But the traffic is annoyingly consistent though—just when you think you can go, suddenly a string of cars show up (my friend Chuck would say they exhibit a Poisson distribution). In retrospect, it's not that surprising that I nearly caused two accidents today. In my defense, the preponderance of trees (real trees, not stalk like palm trees) and hills (hills, people! Hills! Not the unending flatness of South Florida) makes for some challenging sightlines.

In the first near-accident I was trying to drive through an intersection (no traffic light) and narrowly missed being T-boned by a car (oops). The second near-accident happened as I was pulling out of The Red House Inn parking lot and nearly T-boning a passing car (oops).

Self-driving cars can't get here quick enough.

---

Extreme lawn ornaments, Brevard edition

Some people decorate their lawns with garden gnomes. Others use plastic pink flamingos.

In Brevard, it appears cows are the lawn ornaments of choice.

Thursday, October 30, 2014

The Devil gets his due

Located at milepost 422.4 of the Blue Ridge Parkway, the Devil's Courthouse has a short but strenuous trail climbing a half mile to its peak with wonderful panoramic mountain views (see photo above). The mostly paved trail starts from the overlook parking area beside the mountain.

Devil's Courthouse, North Carolina

A “strenuous trail” it says. A “half mile to its peak” it says. “Mostly paved.”

Ha!

Strenuous for someone used to hiking mountain trails. Pure insanity for someone used to the flat paved parking lots of Florida.

Sure, it's mostly paved. I would say about two-thirds of the way up is paved, at an incline of 13° (I measured it with an app on my smartphone), which doesn't sound like much, but you try to walk over a quarter mile on a 13° incline. Every ten feet or so is a small bump across the paved path. I suspect it's to stop people when they stumble and start rolling downhill.

The last third or so of the path is gravel and loose rocks at the same 13° incline, making a fun game of “Break the Ankle!” And then, when you think it can't get any worse—stairs!

“Strenuous” indeed!

---

The day started out beautifully. Not a cloud in the sky, a bit brisk, and a leasurely drive out of Brevard, up US-276 North to the Blue Ridge Parkway. The drive along US-276 was an explosion of colors here and there—we definitely caught the tail end of Peak Leaf Season.

Once on the Blue Ridge Parkway, we stopped at the Pisgah Inn for lunch. Bunny ordered the Turkey, Brie and Apple Wrap with a side of pumpkin soup (“It's like slurping a pumpkin pie,” she said) and I ordered the char broiled whole trout, filleted tableside. It was quite delicious.

After lunch (desert—homemade blackberry cobbler), we headed south along the Blue Ridge Parkway towards the Devil's Courthouse. The drive was nerveracking. All I wanted to do was rubberneck at the passing vistas around every curve, but at the same time, I couldn't move my eyes off the road, lest I launch headlong into a cliff or worse, launch headlong off a cliff. Bunny was trying her best not to “Ohh” and “Ahh” too much.

We did stop a few times at some overlooks. At one, we caught two guys tracking a bear with hand-held radio equipment (it became clear that the bear must have been radio tagged) and a serious camera. Bunny and I never did see the bear.

Eventually, we reached our destination, The Devil's Courthouse.

Well, the base of The Devil's Courthouse. We still had that halfmile hike to contend with.

---

Once you reach the top, the view is spectacular!

---

You would think that once at the top, it would be easy going down. The stairs were hard, seeing how they were broken slabs of rough hewn rock. Then the gravel portion was tricky to keep your foot from shooting out from beneath you on loose gravel. But in an ironic twist, walking down that 13° paved incline was just as bad as going up. You have to lean back to keep from tumbling down, so your feet plop down at this extended angle that's tiring. It's a different tiring than trugding up the trail, but it's tiring nonetheless. I actually found it easier to walk backwards down the trail, but as Bunny mentioned, you can't see where you are going.

Did I mention that view?

---

Sean of the Shorn Locks

And because a few of you asked to see the results of my recent haircut, here you go:

Taken as I rested on the never-ending half-mile mountain trail from Hell.

---

Extreme window displays, Brevard edition

Presented entirely without context (because I saw it entirely without context): a bear wearing a blonde wig.

Friday, October 31, 2014

Easy does it

Bunny and I were still a bit sore from yesterday's small hike so we took it a bit easy today. We just walked a few blocks to downtown Brevard, had lunch, did a bit of shopping, and headed back to The Red House Inn, where I did a Nestea plunge into the bed. A few minutes later, Bunny informed me I had slept for about an hour.

Oh.

We finally ate at The Square Root, which was, as always, very good.

---

Extreme teddy bears, Brevard edition

It's not every day you get to see a life-sized teddy bear just sitting on a park bench. Unless you happen to be in Brevard, in which case, you will see a life-sized teddy bear just sitting around.

• Current
• Next
• Previous
• First
• Last
• Top
• Home
• About
• Archive
• Search
• Glossary
• Copyright
• Help
• Accessibility

Obligatory Picture

Obligatory Contact Info

• Comments? sean@conman.org

Obligatory Feeds

• RSS Feed
• Atom Feed
• JSON Feed

Obligatory Links

• Flutterby!
• KIRK.is

Obligatory Miscellaneous

• About the Source Code
• Source Code

Obligatory AI Disclaimer

No AI was used in the making of this site, unless otherwise noted.

Copyright © 1999-2024 by Sean Conner. All Rights Reserved.