in reply to Re^4: [OT] The interesting problem of comparing bit-strings. (More info.)
in thread [OT] The interesting problem of comparing bit-strings.
Might be that I'm totally wrong, but I think that as long as you're trying to consider
1. Incrementing haystack by 1-bit.
an important primary op, there's something wrong.
I'd basically try to first find out how the needle would need to be shifted in order to match the char_aligned haystack, and leave the haystack as it is - always.
My somewhat naive approach would be to start with building the set of 256 possible 'needle heads' (going for char operations all over). A 'needle head' could be say 8 chars long (or some other convenient value).
Then, look for the occurences of the needle_heads within haystack. For each needle_head, you know the offset (needed shift) associated with it. (Yes, that means 256 searches instead of 1, but it still might be better than shift-ing things around for every next bit-position.)
If needlehead is found, go on with a full, char-wise compare, with haystack's chars untouched and every next needle-char obtained via a proper shift from the next two chars of the needle.
End of string is bit-masked as needed to comply with the known offset.
Maybe you've tried something like that already?
Krambambuli
---
1. Incrementing haystack by 1-bit.
an important primary op, there's something wrong.
I'd basically try to first find out how the needle would need to be shifted in order to match the char_aligned haystack, and leave the haystack as it is - always.
My somewhat naive approach would be to start with building the set of 256 possible 'needle heads' (going for char operations all over). A 'needle head' could be say 8 chars long (or some other convenient value).
Then, look for the occurences of the needle_heads within haystack. For each needle_head, you know the offset (needed shift) associated with it. (Yes, that means 256 searches instead of 1, but it still might be better than shift-ing things around for every next bit-position.)
If needlehead is found, go on with a full, char-wise compare, with haystack's chars untouched and every next needle-char obtained via a proper shift from the next two chars of the needle.
End of string is bit-masked as needed to comply with the known offset.
Maybe you've tried something like that already?
Krambambuli
---
In Section
Seekers of Perl Wisdom