[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