The Advisory Boar

By Abhijit Menon-Sen <>

Who invented the slicing-by-N CRC32 algorithm?

One of my contributions to Postgres 9.5 (back in 2015) was a two-stage optimisation of the CRC computation code. First, switching to a faster algorithm; and second, to use the Intel SSE4.2 CRC instructions where available. I was delighted to have the opportunity to implement such a dramatic performance improvement (CRC computation used to be at the top of the profile on every streaming replica by some distance).

Optimising something by writing assembly (even if it was only a couple of instructions, later replaced by compiler intrinsics) is always fun, but here the algorithm change was also a substantial improvement, in that it used a lookup table to process eight input bytes at a time. This technique is known as “slicing-by-N” (where N depends on the size of the lookup table), and was originally described here:

Frank L. Berry, Michael E. Kounavis, "Novel Table Lookup-Based Algorithms for High-Performance CRC Generation", IEEE Transactions on Computers, vol. 57, no. , pp. 1550-1560, November 2008, doi:10.1109/TC.2008.85

This paper, having been published in a prestigious IEEE journal, is of course not easily available for download (not when I looked in 2015, and apparently not today). I was able to find what I needed to implement the technique thanks to other reference materials, notably including Stephan Brumme's Fast CRC32 page (now considerably expanded since 2015), but I never actually got to read what Messrs. Kounavis and Berry had to say about their technique.

Recently, I had occasion to look at CRC32 implementations again, and I found a different paper that I had looked at briefly the last time: Cyclic Redundancy Check Generation Using Multiple Lookup Table Algorithms by Indu I. and Manu T.S. from TKM Institute of Technology, Kollam, in Kerala (my mother's home state in South India). I remember noting that there was something odd about the paper, but not having time enough to give it more than a passing glance. This time, I spent a while reading it, and it's certainly very odd.

ABSTRACT: The primary goal of this paper is to generate cyclic redundancy check (CRC) using multiple lookup table algorithms. A compact architecture of CRC algorithm (Slicing-by-N algorithm) based on multiple lookup tables (LUT) approach is proposed. This algorithm can ideally read large amounts of data at a time, while optimizing their memory requirement to meet the constraints of specific computer architectures. The focus of this paper is the comparison of two algorithms. These two algorithms are Slicing by-N-algorithm and Sarwate algorithm, in which slicing by-N-algorithm can read arbitrarily 512 bits at a time, but Sarwate algorithm, which can read only 8 bits at a time. This paper proposes the generation of CRC using slicing by 8 algorithm. In this, message bits are chunked to 8 blocks. All are processed at a time. Proposed Slicing-by-8 algorithm can read 64 bits of input data at a time and it doubles the performance of existing implementations of Sarwate algorithm.

Is this paper claiming to have invented the slicing-by-N algorithm? It's hard to tell from the blather in the abstract, but going through the remaining blather (and effort that, in retrospect, I cannot in good conscience commend to the reader) suggests that this is indeed the case.

Recently time is the major concern. So in order to process large amount of data at a time, Multiple Lookup based approach is more efficient. Multiple Lookup based approach contains five CRC algorithms, called Slicing by-N algorithm (N ϵ 4, 8, 16, 32, 64), which is used to read up to 512 bits at a time. So performance of the system should be increased. Here proposing Slicing by-8 algorithm to read 64 bits at a time. Here proposed an efficient design of CRC generator using Slicing by-N algorithm (N=8). In this algorithm, input message stream is sliced into N slices and each slice has 8 bits. So using this Slicing by-8 algorithm, it can read 64 bits at a time and it triples the performance of existing implementation of Sarwate algorithm.

Oho, so it triples the performance of existing implementations of the Sarwate algorithm, does it? Funny the abstract claims a paltry doubling in performance then. The paper goes on to describe CRC computation with block diagrams, and then has some more blather about VHDL and MATLAB and some screenshots of “simulation waveforms”, all of which seems to amount to showing that the various CRC algorithms produce the same results and that processing more input bytes at a time is faster than not doing so. I made judicious use of the fast-forward button to reach the conclusion, which begins with

The design of CRC generator using Multiple Look Up based approach is proposed. In this paper, slicing by-8 algorithm is designed, and compares this algorithm with the existing algorithms, that is, with Sarwate algorithm and LFSR method.

So yeah, they're claiming in a slightly roundabout way to have invented the slicing-by-8 CRC algorithm. However, the authors cite the Kounavis and Berry paper anyway, perhaps so that any criticism can be blamed on some sort of unfortunate misunderstanding. I didn't find any citations of this paper in the minute or two I spent on the search, but Citeseer and Researchgate link to it, and it's quite prominent in search results, so it's probably only a matter of time before someone cites it.

The paper was published in "International Journal of Modern Engineering Research” (ijmer.com) in 2012; the journal's name alone reminded me of the scammers, Academic Journals Online, whom I encountered a few years ago. IJMER does not, however, appear to be one of the AJO journals. Perhaps it's a second cousin.

Unfortunately, the authors include no contact information in the paper, so I was not able to send them a link to this page.

Malicious pollution reports

Before we installed a towel rail in the bathroom, we kept clean clothes on an old newspaper on the washbasin counter while bathing. It kept the clothes dry and kept me entertained while brushing my teeth for several months (I would unfold and refold it differently every few days when the top stories began to seem familiar).

Pollution report malicious, incorrect: Javadekar” dated June 7, 2016 quoted the reaction of the Union Minister for Environment, Prakash Javadekar, to a paper that was widely reported with headlines like “Life expectancy in Delhi has reduced by six years because of air pollution, reveals study”. Here's a clipping:

Pollution report malicious, incorrect: Javadekar

The original paper, “Premature mortality in India due to PM2.5 and ozone exposure”, written by scientists at IITM Pune and published in Geophysical Research Letters, was not immediately available for download. The Minister's scathing indictment shows that he is only too aware of the threat posed by Elsevier journals.

Of course, this is hardly the first attempt to maliciously target India with overblown pollution reports:

Volcanic activity in modern-day India, not an asteroid, may have killed the dinosaurs, according to a new study.

Tens of thousands of years of lava flow from the Deccan Traps, a volcanic region near Mumbai in present-day India, may have spewed poisonous levels of sulfur and carbon dioxide into the atmosphere and caused the mass extinction through the resulting global warming and ocean acidification, the research suggests.

Barely a month after his astute recognition of this pattern, however, a cabinet reshuffle saw Prakash Javadekar reassigned to the Ministry of Human Resources and Development.

(Aside: “Javadekar does a U-turn after questioning pollution study”.)

One month after demonetisation

A little over a month ago, our Glorious Leader eliminated corruption, black money, terrorism, and poor people in one bold and innovative move by declaring most of the currency in circulation to not be legal tender.

We are fortunate that we can get by without much cash in hand. We eat mostly what we grow, or is grown nearby in the village, and what few additional expenses we have (e.g., milk) have so far been met by the ten— and twenty-rupee notes we had collected to save time by paying exact tolls on the highway.

Our one visit to the nearest bank yielded a two-thousand rupee note and a bag of coins each—the most the branch could spare per person, given that they've received no cash for several days.

In Delhi, Ammu is not so lucky. Her landlord demands the rent in cash, and in exam season, she has had to stand in queue for several hours at an ATM to withdraw a quarter of her rent (which is the maximum one can withdraw in a day). Strangely, the vegetable and fruit sellers in her locality do not accept digital payments yet.

I was looking forward to hearing what the Supreme Court of India had to say about demonetisation, but they haven't said much, because they're busy with matters of real importance to the nation, like how often the national anthem should be played and how straight one should stand to properly demonstrate one's “constitutional patriotism”.

Decathlon.in: terms of disservice

I wanted to buy a jacket from Decathlon, so I went to create an account on their site, which involved wading through as convoluted and boring a "terms of use" statement as I've ever seen. (Alas, I can't link to it because it's just in a textarea on the account creation page.)

Most of the terms were unremarkable (obnoxious and officious, but still unremarkable), until I encountered this gem about halfway down.

«11. The Buyers shall be responsible to up keeping the providing information relating to the products proposed to be sold by Us. In this connection, The Buyers undertake that all such information shall be secured in all respects. The Buyers shall not defame the attributes of such products or services so as to mislead other Buyers in any manner.»

I created an account anyway (and the jacket is rather nice), but I didn't want to be responsible for “up keeping” information relating to the products they sell. So I wrote to their customer support to ask what this ridiculous verbiage was supposed to mean. Much to my surprise, they not only responded to my mail, but actually asked their lawyers for a clarification.

I had a word with our legal department and they mentioned that the clause means if a customer has an issue with or an opinion about a product, they contact us first for us to help them with their issue and not post it on social networking sites or the media.

Not being a fan of idiotic and underhand (and poorly-written, to boot) attempts to restrict what one's customers can and cannot say, I tried to delete my account. The terms of service said I could delete my account at any time, but I could find no way to do so on the web site. So I asked Decathlon to delete my account.

First they said they had deleted my account. I could still login, so I wrote back to ask them to delete it again. Then they said that I had registered two accounts (which I had not; I had just changed my name to "ABC" in my profile), and asked me to send them a list of addresses I had used (which I did—one address). Then they stopped answering my mail.

Eight weeks later, I can still login to my account.

Technically, I don't think this post violates their terms of service, because I did contact them for help first. But they do have a stern profanity policy, so here's a little something to help the account suspension process along: What the fuck, Decathlon? You're a bunch of incompetent nincompoops!

Update (2016-12-13): The account still works, but the “you may delete your account at any time” clause has been removed from the terms of use at some point. Of course, the vital “responsible to up keeping the providing information” clause is still there.

Metro station robbery: redux

Ramit's police complaint (made by way of some suitable boffin) resulted in the police going to the station the next day and arresting two people expanding their cellphone collection by the same means as before. They may not be the same people whom Ramit met, but the indications are that at least ten people are involved and—as we suspected—this is something that has been going on for a while.

I wonder if the earlier victims complained to the police. It's hard to believe that none of them did; so perhaps their complaints arrived too lown down the police hierarchy to prompt any serious action.

But I hope the cops find every one of the robbers now.

Armed robbery outside a Delhi Metro station

Ramit was robbed of his mobile phone by four armed men on two scooters with no license plates at 0730 this morning, while waiting outside the New Ashok Nagar Metro station for me to pick him up on our way to the Okhla Bird Sanctuary. When he handed over his phone, they immediately discarded the SIM (which he recovered), and left. Fortunately, Ramit was not hurt.

We drove to the Police Chowki nearby, but there were no policemen there. Some hours later, we returned to the Metro station and spoke to the CISF personnel in charge of security. They said they would have tried to help if we had reported the crime immediately, but that they were responsible for security only inside the station premises. The CISF superintendent told us to file a complaint at the Yamuna Bank police station, and also said there had been other thefts in the area recently, but the Delhi Police personnel deputed to patrol the outside of the station never turned up as scheduled.

I submitted a report of the incident as feedback on the Delhi Metro web site, and also called them up and spoke to a Ms. Rita Kumar at the DMRC to report the robbery. She promised to "forward" the information I gave her, for whatever that is worth, but again said that incidents outside the station were solely the problem of the Delhi Police.

Aside: the Metro station in question is (like many others) an elevated structure built around a platform. The road passes under it, and Ramit was waiting there on the sidewalk in front of a pillar with a "Station Entry" sign on it. While it may technically be outside the premises of the station, it seems somewhat irresponsible for the DMRC to wash its hands of security directly underneath the station, barely thirty metres from the entrance.

Despite his traumatic morning, Ramit (who says he has been mugged before in Nairobi) wanted to stick to our plan, and we had a nice bird-watching session at Okhla and Khadar. Notable sightings include the first Citrine Wagtail of the black-backed calcarata race this season, close-up views of Black-breasted Weavers, four Ferruginous Pochards, and a number of White-tailed Stonechats, Striated Babblers, and Graceful Prinias. I also relished the opportunity to study various species of grasses in detail.

Spam sent through The Hindu web site

I just received a Nigerian scam email sent through some "forward this article" feature on The Hindu web site. Here's the message, slightly edited:

Return-Path: <thehindu@vsnl.com>
…
Received: from web1.hinduonnet.com (web1new.hinduonnet.com [127.0.0.1])
	by web1.hinduonnet.com (8.13.5/8.13.5) with ESMTP id
	o7SMbdhC026146; Sun, 29 Aug 2010 04:07:39 +0530
Received: (from apache@localhost)
	by web1.hinduonnet.com (8.13.5/8.13.5/Submit) id
	o7SMbRAc026122; Sun, 29 Aug 2010 04:07:27 +0530
Date: Sun, 29 Aug 2010 04:07:27 +0530
Message-Id: <201008282237.o7SMbRAc026122@web1.hinduonnet.com>
From: thehindu@web1.hinduonnet.com
Reply-To: virtososchulks@yahoo.com
Subject: Article from  The Hindu: Sent to you by Virtosos  Chulks.
From: The.Manager@web1.hinduonnet.com
To: undisclosed-recipients:;

International Commercial Bank Ghana
First Light Branch
Accra, Ghana.

Sir,   

I got your contact during my search for a reliable, trust worthy and
honest person to introduce this transfer project with. My name is Mr.
Virtosos Chulks. I am the manager of the International Commercial Bank
Ghana, First Light Branch Accra. I am a Ghanaian married with two kids.

I am writing to solicit your assistance in the noble transfer of
US$5.500.000.00.
…

No, that's not a mistake—there really are two From: fields. But that's probably the least broken thing about a feature that allows people to send arbitrary email messages (with no reference to an article in The Hindu, by the way) through their site.

I wrote to thehindu@vsnl.com (which is also the contact address given on their web site) to report the problem. At least my mail did not bounce. I wonder if anyone will pay attention to it.

Exide warranty nightmare

Our UPS is hooked up to three Exide Powersafe EP65-12 SLA (Sealed Lead Acid) batteries. Normally, that gives us about six hours of backup time for my desktop, monitor, and a few assorted peripherals. It's not often that the mains power is off for so long (less than half a dozen times a year, I'd guess), but that capacity has proven invaluable in the past. For the last few months, however, the UPS has lasted for half an hour at most, even when the batteries were fully charged. Using a multimeter, I found that the voltage across one of the batteries fell rapidly to 10.5V just before the UPS died, while the other two remained above 12V. Since the batteries were still under warranty, I contacted the vendor to ask about having them replaced (which I have had to do in the past)

Unlike last time, the vendor told me to register a complaint with Exide, which I did after some delay due to external circumstances. An engineer was dispatched to visit me a couple of days later, and after testing the system, he agreed with my diagnosis: one battery was bad. He wrote up a report and went on his way after telling me that the replacement should arrive in a few days. Unfortunately, what did arrive the next day was email from his supervisor, saying they couldn't replace the battery because the charging current was "too low". (The mail also said that I didn't have the original invoice for the purchase of the batteries, but that was just the engineer trying to cover his ass after forgetting to ask me for it.)

Read more…

Nonsensical DoT crypto restrictions

What are the regulations governing the use of cryptography and the development of cryptographic software in India? The answer is either "there aren't any" or "nobody really knows".

One of the few official documents to discuss the subject is this one ("Guidelines and general information for setting up of international gateways for internet") published by the Department of Telecommunications (DoT) in 2001. It is not clear why an informative document inviting proposals from ISPs to set up international gateways should have anything to say about the use of cryptography in general, or whether this amounts to a rule, but here's the relevant section:

II. LEVEL OF ENCRYPTION

Individuals/Groups/Organisations are permitted to use encryption upto 40 bit key length in the RSA algorithms or its equivalent in other algorithms without having to obtain permission. However, if encryption equipments higher than this limit are to be deployed, individuals/groups/organisations shall do so with the permission of the Telecom Authority and deposit the decryption key, split into two parts, with the Telecom Authority.

There has been plenty of criticism of this section as being "too weak", but the real problem is that it's stupid and wrong (as I have explained in email one too many times; hence this post).

Read more…

Harike survey reporting: responsible journalism at its finest

Someone sent me a link to a story in the Indian Express that creatively distorts quotes extracted from my informal report on Harike to try and make the case that the survey was a waste of time and money. The article is by a Dharmendra Rataul, dated today. I can't figure out if it was published in the newspaper, or only online.

I just love how terribly official the article makes everything sound. Instead of saying “Some chap who was at Harike wrote email to a public list, and someone sent me a copy”, the article begins thus:

The controversy over the census of migratory birds at Harike wetland took a new turn on Monday when a member of the Census Committee constituted by the state wildlife department traced serious lacunae in the process. Abhijit Sen, a bird watcher who was on the census panel, has stated in a letter (sent via e-mail) to the Chandigarh Birds Club (CBC), the nodal agency that helped conduct the survey, that he was sad that the entire exercise was like a “free vacation”.

Nobody told me that a Census Committee (or was it a panel?) had been constituted, much less that I was a member of it. The Chandigarh Birds Club (which, as far as I know, is just a mailing list) becomes a "nodal agency" with its own acronym. Email becomes a letter, which The Indian Express has mysteriously obtained a copy of. But the best part is that my trip report is made to sound like some weighty official critique (lacunae!), when I wrote right at the beginning that:

My memories of the time I spent at Harike are already fragmented, and I don't feel up to writing another exhaustive report. Instead, here's a selection of the more vivid moments that I will remember the trip by—not in any particular order, and with no attempt to fill in the fuzzy grey areas in between.

Having selected such a solid foundation for his news report, Mr. Rataul goes on to disingenuously reorder two carefully-selected sentences from my (approximately four thousand word) report.

“Sadly I noticed that many people who had volunteered to help with the survey treated the entire exercise as a little more than a free vacation,” he has stated in the letter, a copy of which is The Indian Express (sic). He said he noticed a similar attitude during surveys at the Pong Dam (Himachal) too. “A total count (of birds) was impossible in the circumstances,” he stated.

In my report, the second sentence is in a different paragraph from the first one, and refers to a completely different set of circumstances, which I enumerate: “…because a total count was impossible in the circumstances (distance, rocking boat, lots of movement in the flocks), we sampled parts of the flock…”. Anyway, I was using "total count" in its technical sense where bird surveys are concerned. A little basic research would have told Mr. Rataul that total counts of flocking birds in large areas is often not possible, no matter how many scientists are present.

I notice, too, that "I was sad that P treated X as Y” has been summarised as “I was sad that X was Y”. But the article does not, of course, mention what I said in a subsequent "letter" in response to a comment about the "free vacation" bit.

It is true that there were people at Harike who did not take the survey seriously, but that is a potential risk with any volunteer-based survey effort. It is regrettable, and I hope that steps can be taken in future to make participants more aware of the methodology and implications of the work they're doing, and thus take it more seriously.

But I can also say that there were serious, interested birders at Harike who did their sincere best during data collection, and I don't think that the funds have "gone down the drain" at all. Every census, whether conducted by volunteers or professionals, has sources of error and scope for improvement. Just because I pointed out one problem does not mean that the entire effort was a waste.

I had never heard of Mr. Rataul, so I looked at some of the other articles he's written for IE. In an earlier story about the Harike survey, he says: “The majority of the birds are gray-legged geese, though bar-headed geese, mallard duck, pin-tale duck, porchid, varieties of avifauna, pelicans, flamingoes and teals have also been spotted.”

I realise it's unfair to expect a journalist these days to know anything about the subject he's covering, but really, where on earth did he find a word like "porchid"? And does he think "avifauna" is a specific kind of bird, like "geese"?

Anyway, with all the integrity and competence evident in Mr. Rataul's articles, I should consider myself fortunate that he at least managed to get my name right… oh, wait, scratch that. I guess correctly cutting and pasting my name from an email was also beyond him.

(I sent a complaint to editor@expressindia.com, but my mail bounced because "Database disk quota exceeded".)