[CWB] [ cwb-Bugs-2791118 ] bitfield comparison functions may return
unintuitive results
SourceForge.net
noreply at sourceforge.net
Thu Aug 27 15:32:48 CEST 2009
Bugs item #2791118, was opened at 2009-05-13 11:03
Message generated for change (Comment added) made by nobody
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=2791118&group_id=131809
Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: CL low-level library
Group: None
Status: Pending
Resolution: None
Priority: 5
Private: No
Submitted By: Klaus Rothenhusler (rothenha)
Assigned to: Stefan Evert (schtepf)
Summary: bitfield comparison functions may return unintuitive results
Initial Comment:
As bf_equal(Bitfield bf1, Bitfield bf2) and bf_compare(Bitfield bf1,
Bitfield bf2) check for the equality of all the memory allocated for
*field including non relevant bits they may return false even though the
relevant bits are all equal. The following minimal example is meant
to demonstrate this:
#include <stdio.h>
#include "bitfields.h"
int main(int argc, char **argv) {
int i;
Bitfield bf1 = create_bitfield(10);
Bitfield bf2 = create_bitfield(10);
for (i=0; i<10; ++i) {
set_bit(bf1, i);
}
set_all_bits(bf2);
// prints 0
printf("%d\n", bf_equal(bf1, bf2));
destroy_bitfield(&bf1);
destroy_bitfield(&bf2);
exit(0);
}
This is not what is intended I believe. The solution I use is to
compare the full cells BFBaseType-wise and if the Bitfields have an
additional field I shift them so both may only differ in the relevant
bits:
int bf_equal(Bitfield bf1, Bitfield bf2)
{
int i, max, shift;
BFBaseType res;
assert(bf1->bytes == bf2->bytes);
max = bf1->elements / BaseTypeBits;
for (i = 0; i <max; i++)
if (bf1->field[i] != bf2->field[i])
return 0;
shift = BaseTypeBits - bf1->elements % BaseTypeBits;
if (shift != BaseTypeBits) {
res = (bf1->field[max] << shift) ^ (bf2->field[max] << shift);
return !res;
}
return 1;
}
int bf_compare(Bitfield bf1, Bitfield bf2)
{
int i, max, shift;
BFBaseType res;
assert(bf1->bytes == bf2->bytes);
max = bf1->elements / BaseTypeBits;
for (i = 0; i <max; i++) {
if (bf1->field[i] - bf2->field[i] < 0)
return -1;
else if (bf1->field[i] - bf2->field[i] > 0)
return 1;
}
shift = BaseTypeBits - bf1->elements % BaseTypeBits;
if (shift != BaseTypeBits) {
res = (bf1->field[max] << shift) - (bf2->field[max] << shift);
return res;
}
return 0;
}
Regards
--Klaus
----------------------------------------------------------------------
Comment By: Nobody/Anonymous (nobody)
Date: 2009-08-27 13:32
Message:
Thanks for the nice fix.
I ran into this bug when developing code to identify colligations running
on top of the CWB. So the CWB source is not affected anywhere else. I only
needed bf_equal() so I didn't realise bf_compare() doesn't return anything
useful.
----------------------------------------------------------------------
Comment By: Stefan Evert (schtepf)
Date: 2009-08-17 19:34
Message:
Thanks for the detailed report.
I have corrected the implementation, though in a different way using a bit
mask, which remains closer to the original code. Please test!
Where did you run into this problem? I cannot find any place in the CWB
source code where these functions are actually used (and I very much doubt
that bf_compare() returns any sensible value because it takes the
difference of two unsigned chars, which shouldn't be < 0).
----------------------------------------------------------------------
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=2791118&group_id=131809
More information about the CWB
mailing list