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 test case (from the question's code) produced 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 (nor `<stdbool.h>`):
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 same 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.