Before we make any changes, let's add some tests to the end, so we have confidence that we don't break anything that worked:
#include <stdio.h>
static int test(unsigned int value, unsigned int expected)
{
unsigned int actual = findsaw(value);
if (actual == expected)
return 0;
printf("findsaw(%#x) = %u\n", value, actual);
return 1;
}
int main()
{
return test(0x0, 0)
+ test(0xAA, 0)
+ test(0x585, 0)
+ test(0xA0F, 8)
+ test(0xF0A, 0)
+ test(0xFA0, 4)
+ test(0xEAEA476Bu, 23);
}
This all passes (the program returns 0). I made test take the value as an unsigned int, because 0xEAEA476B is too big for a plain int on my system.
Now let's look at your code.
#include <stdio.h>
#define YES 1 /* inside a sequence */
#define NO 0 /* outside a sequence */
We're not using anything from <stdio.h>, so that's not required. Also, instead of defining YES and NO in the preprocessor, we could include <stdbool.h>, and then use true and false instead.
unsigned int findsaw(int value) {
unsigned int sequence = value;
Are you required to accept input as a signed integer? If not, then declare findsaw() to take an unsigned int. As it is, the last testcase triggers a compilation warning, as 0xEAEA476BL is larger than INT_MAX on my system.
unsigned char idx = 0;
unsigned char sequenceIdx = 0;
unsigned char currentIdx = 0;
unsigned char size = 0;
unsigned char sequenceSize = 0;
unsigned char bit = value & 1;
unsigned char nextBit;
None of these really need to be char. It's probably better to let them be int (or uint_fast8_t if you're really keen).
These names aren't immediately obvious to me (or to you in six months' time). It might be worth grouping them so that idx and size, which represent the best match so far, are placed together, with a comment explaining that. Similarly, sequenceIdx and sequenceSize seem to represent the current in-progress match, and should go together.
Some of the naming was alien to me: I'd have considered what you call the "next" bit to be "current", and what you call just "bit" to be "last_bit". That might be just me, though.
if (bit ^ nextBit) {
A comment would be nice here: this is true when we're matching the sawtooth pattern. Also, the else branch contains actions that are only needed immediately at the end of a sequence, and do nothing for extended runs such as 0x00 or 0xFF, so that can be else if (insideSequence).
We can save a bit of work here:
/* matched a transition */
if (insideSequence) { /* just add to the size */
sequenceSize++;
} else {
/* initialize for inside a sequence */
sequenceSize = 2;
sequenceIdx = currentIdx;
insideSequence = true;
}
If we initialise sequenceSize to 1 instead of 0, then we can simply increment it in both cases (i.e. outside the if). We can use sequenceSize == 1 to determine whether we're in a sequence, and we no longer need the insideSequence variable:
unsigned int findsaw(unsigned int value) {
unsigned int sequence = value;
/* best match so far */
unsigned int best_start = 0; /* this is what we're looking for */
unsigned int best_size = 0;
unsigned int sequenceIdx = 0;
unsigned int currentIdx = 0;
unsigned int sequenceSize = 1;
while (sequence) {
const int last_bit = sequence & 1;
sequence >>= 1;
const int current_bit = sequence & 1;
if (last_bit ^ current_bit) {
/* matched a transition */
if (sequenceSize++ == 1) {
/* the start of a new sequence */
sequenceIdx = currentIdx;
}
} else if (sequenceSize != 1) {
/* not matched - did we just finish a sequence? */
if (best_size < sequenceSize) {
best_size = sequenceSize;
best_start = sequenceIdx;
}
sequenceSize = 1;
}
++currentIdx;
}
if (best_size < sequenceSize) {
best_start = sequenceIdx;
}
return best_start;
}
Let's see if we can do anything about the duplication of if (best_size < sequenceSize) when we reach the last bit. I'll add a couple of extra tests:
+ test(0x50000005u, 27)
+ test(0xA0000005u, 0)
The last one fails (returns 28), because we are zero-extending the left of the value, but not the right. If we simply take out the test, then other test cases fail (0xa0f and 0x50000005). It seems that the while (sequence) returns too early in those cases.
At this point, I give up fixing this and look at a different approach. We don't need to check last_bit ^ current_bit every time around the loop - we can compute them all at the some time like this:
unsigned int sequence = value;
unsigned int mask = sequence ^ (sequence >> 1);
This produces a 1 everywhere we have a bit preceded by its complement. We still have the problem that the high bit might be set, but we can fix this by writing mask = sequence ^ (sequence << 1) to make the low bit the stray one, and we can just shift that out. Now, all we have to do is find the longest run of 1s:
unsigned int findsaw(unsigned int value)
{
unsigned int sequence = value;
unsigned int mask = sequence ^ (sequence << 1);
/* best match so far */
unsigned int best_start = 0; /* this is what we're looking for */
unsigned int best_size = 0;
/* current run */
unsigned int current_start = 0;
unsigned int current_size = 0;
/* current position */
for (unsigned int i = 0; mask >>= 1; ++i) {
if (mask & 1) {
if (!current_size++)
/* the start of a new run */
current_start = i;
} else if (current_size) {
current_size = 0;
}
if (current_size > best_size) {
best_size = current_size;
best_start = current_start;
}
}
return best_start;
}
#include <stdio.h>
static int test(unsigned int value, unsigned int expected)
{
unsigned int actual = findsaw(value);
if (actual == expected)
return 0;
printf("findsaw(%#x) = %u\n", value, actual);
return 1;
}
int main()
{
return test(0x0, 0)
+ test(0xAA, 0)
+ test(0x585, 0)
+ test(0xA0F, 8)
+ test(0xF0A, 0)
+ test(0xFA0, 4)
+ test(0xEAEA476Bu, 23)
+ test(0x50000005u, 27)
+ test(0xA0000005u, 0);
}
All the tests pass; time to go home.
