Re: [B.A.T.M.A.N.] [PATCH] batman-adv: Fixing wrap-around bug in vis

[Sven Eckelmann <sven.eckelmann@gmx.de>]

[-- Attachment #1.1: Type: Text/Plain, Size: 1670 bytes --]

Sven Eckelmann wrote:
> Sven Eckelmann wrote:
> > Now it gets real cruel, but who cares... C++ wasn't accept in the kernel,
> >  so we have to deal with it using some GNUish stuff.
> >
> > #define seq_before(x,y) ({typeof(x) _dummy = (x - y); \
> >                           _dummy > 1u << (7u + 8u * (sizeof(_dummy) -
> >  1u));}) #define seq_after(x,y) ({typeof(x) _dummy = (y - x); \
> >                          _dummy >= 1u << (7u + 8u * (sizeof(_dummy) -
> >  1u));})
> 
> After a small discussion with Marek I would like to suggest a easier
>  readable and symmetric definition
> 
> /* Returns the smallest signed integer in two's complement with the sizeof
>  x */
> #define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))
> 
> /* Checks if a sequence number x is a predecessor/successor of y.
>    they handle overflows/underflows and can correctly check for a
>    predecessor/successor unless the variable sequence number has grown by
>    more then 2**(bitwidth(x)-1)-1.
>    This means that for an uint8_t with the maximum value 255, it would
>  think: * when adding nothing - it is neither a predecessor nor a successor
>  * before adding more than 127 to the starting value - it is a predecessor,
>  * when adding 128 - it is neither a predecessor nor a successor, * after
>  adding more than 127 to the starting value - it is a successor */ #define
>  seq_before(x,y) ({typeof(x) _dummy = (x - y); \
>                          _dummy > smallest_signed_int(_dummy); })
> #define seq_after(x,y) seq_before(y,x)

@Linus: Here a small testcase - just as prove that I tested it this time :D

Best regards,
	Sven

[-- Attachment #1.2: seq_before_test.c --]
[-- Type: text/x-csrc, Size: 3082 bytes --]

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>


/* Returns the smallest signed integer in two's complement with the sizeof x 
*/
#define smallest_signed_int(x) (1u << (7u + 8u * (sizeof(x) - 1u)))

/* Checks if a sequence number x is a predecessor/successor of y.
   they handle overflows/underflows and can correctly check for a
   predecessor/successor unless the variable sequence number has grown by
   more then 2**(bitwidth(x)-1)-1.
   This means that for an uint8_t with the maximum value 255, it would think:
    * when adding nothing - it is neither a predecessor nor a successor
    * before adding more than 127 to the starting value - it is a predecessor,
    * when adding 128 - it is neither a predecessor nor a successor,
    * after adding more than 127 to the starting value - it is a successor */
#define seq_before(x,y) ({typeof(x) _dummy = (x - y); \
                         _dummy > smallest_signed_int(_dummy); })
#define seq_after(x,y) seq_before(y,x)

#define type uint8_t

int main(void) {
	int first_round = 1;
	type x, y, i;
	type parts = ((type)~0u >> 1); /* 2**(bitwidth(type)-1)-1 */
	int error = 0;

	for (x = 0; first_round || x != 0; x++) {
		first_round = 0;

		y = x;

		/* Equal */
		{
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Successor */
		for (i = 0; i < parts; i++) {
			if (!seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Undefined */
		{
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == true\n", x, y);
				error = 1;
			}
			y++;
		}

		/* Predecessor */
		for (i = 0; i < parts; i++) {
			if (seq_before(x, y)) {
				printf("Wrong seq_before(%u, %u) == true\n", x, y);
				error = 1;
			}
			if (!seq_after(x, y)) {
				printf("Wrong seq_after(%u, %u) == false\n", x, y);
				error = 1;
			}
			y++;
		}
		
		if (x != y) {
			printf("In round %u only tested till %u\n", x, y);
			error = 1;
		}

	}

	if (first_round) {
		printf("Not done a single test\n");
		error = 1;
	}
	

	/* 0 is successor of 0-1 */
	{
		x = (type)~0u;
		y = 0;
		if (!seq_before(x, y)) {
			printf("Wrong seq_before(%u, %u) == false\n", x, y);
			error = 1;
		}
		if (seq_after(x, y)) {
			printf("Wrong seq_after(%u, %u) == true\n", x, y);
			error = 1;
		}
		y++;
	}
	
	
	/* 0 is predecessor of 1 */
	{
		x = 1;
		y = 0;
		if (seq_before(x, y)) {
			printf("Wrong seq_before(%u, %u) == true\n", x, y);
			error = 1;
		}
		if (!seq_after(x, y)) {
			printf("Wrong seq_after(%u, %u) == false\n", x, y);
			error = 1;
		}
		y++;
	}

	return error;
}

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 836 bytes --]