Thread: I'm back, struggling to visualise how to fix my code

I've added the only snippets that should matter below, as for the context: I'm making my own library and launcher pair (some might remember about that from a long time back), after having finished experimenting with IO APIs and interfaces I finally decided on a long term interface and api that I'd like to use, issue with that is that in the process of that experimentation the codebase became a complete mess.

To fix that I decided to just start from scratch, part of the library requires fallback modes for fixed size integers (to be clear I do not mean fixed bit width), the final fallback mode I never actually noticed I needed until shortly before my decision to start from scratch, I hadn't implemented it back then but I'd like to do so now. That fallback mode is array based, the functions in the 2nd snippet are going to be the common functions I use for that.

I'm trying to do bit rotation without an additional integer to copy into and do simple shifts instead, thing is I'm struggling to map it correctly in my head and I don't want to be stuck on this for ages before I move onto the timestamp code which relies on it to provide a more consistent interface to system provided times (like the millisecond vs nanosecond issues of windows vs linux).

I'm planning to just make the minimum value supported be the quectoseconds (probably spelt that wrong) so that the library doesn't need to worry about that issue again for years - probably centuries even - to come, to that end array based integers are a must for the fallback mode of the 256 bit integers (128bit turned out to be too small) that would be used for it.

I know I did this wrong after managing to do likewise on paper but it's all I got for what I'm doing so far. pawju defaults to uintmax_t and pawku defaults to unsigned __int128, these are all marked inline functions by the PAW_QCK, PAW_FQK (force quick) and QCK (either of them, depends on mapping) macros, EINTSEGW is just the width of the chosen segment mapping (final choice is the pawku/pawkd variants which are the true largest integers the compiler offers). Anyone have any ideas to share here?

The template snippet that's to be replicated in array form:

Code:

QCK EINTVALU EINTU_ROL( EINTVALU n, pawju move )
	{ return (n << move) | (n >> (EINTSEGW - move)); }
QCK EINTVALU EINTU_ROR( EINTVALU n, pawju move )
	{ return (n >> move) | (n << (EINTSEGW - move)); }

The underlying array functions that'll be used for the array based unsigned integers

Code:

PAW_QCK void _pawesegu_move( pawku *upper, pawku *lower, pawju shl, pawju shr )
{
	pawku was = *lower;
	*lower  = *upper >> shr;
	*lower |= *upper << shl;
	*upper  = was >> shr;
	*upper |= was << shl;
}
/* Rotate right */
PAW_QCK void _paweintu__ror( pawku *n, pawju have, pawju move )
{
	pawju movr = move % PAWKD_WIDTH;
	pawju movl = PAWKD_WIDTH - movr;
	pawju jump = (move / PAWKD_WIDTH) % have;
	pawku *dst = n, *src = n, *end = *n + have, tmp = 0;
	for ( src += jump; src < end; ++src, ++dst )
		_pawesegu_move( src, dst, movl, movr );
	for ( src = n; dst < end; ++src, ++dst )
		_pawesegu_move( dst, src, movl, movr );
}

PAW_FQK void _paweintu_ror( pawku *n, pawju size, pawju move )
	{ _paweintu_ror( n, size / sizeof(pawku), move ); }

/* Rotate left */
PAW_QCK void _paweintu__rol( pawku *n, pawju have, pawju move )
{
	pawju movl = move % PAWKD_WIDTH;
	pawju movr = PAWKD_WIDTH - movl;
	pawju jump = (move / PAWKD_WIDTH) % have;
	pawku *dst = n, *src = n, *end = *n + have, tmp = 0;
	for ( src += jump; src < end; ++src, ++dst )
		_pawesegu_move( src, dst, movl, movr );
	for ( src = n; dst < end; ++src, ++dst )
		_pawesegu_move( dst, src, movl, movr );
}

PAW_FQK void _paweintu_rol( pawku *n, pawju size, pawju move )
	{ _paweintu_ror( n, size / sizeof(pawku), move ); }

Never mind, I think I figured out how to do it right (at least in local segment form anyways, the loop still needs to be fixed):

Code:

typedef struct { pawku n[6]; } paweintrotu;
/* Rotate right */
PAW_QCK void _paweintsegu_ror( paweintrotu *rot, pawju shl, pawju shr )
{
	paweintrotu res = {0};
	res.n[0]  = rot->n[4] >> shr;
	/* This order helps the compiler see the load of rot->n[5] only needs to be
	 * done once, we do likewise for the other segments below */
	res.n[5]  = rot->n[5];
	res.n[0] |= rot->n[5] << shl;
	res.n[2]  = rot->n[0] >> shr;
	res.n[1]  = rot->n[1];
	res.n[2] |= rot->n[1] << shl;
	res.n[4]  = rot->n[2] >> shr;
	res.n[3]  = rot->n[3];
	res.n[4] |= rot->n[3] << shl;
	*rot = res;
}
PAW_QCK void _paweintu__ror( pawku *n, pawju have, pawju move )
{
	pawju movr = move % PAWKD_WIDTH;
	pawju movl = PAWKD_WIDTH - movr;
	pawju jump = (move / PAWKD_WIDTH) % have;
	paweintrotu rot = {0};
	pawku *low = n, *top = n + jump, *end = *n + have, *mid = end - jump;
	rot.n[0] = *low;
	rot.n[2] = *mid;
	rot.n[4] = *top;
	for ( src += jump; src < end; ++src, ++dst )
	{
		rot.n[1] = low[1];
		rot.n[3] = mid[2];
		rot.n[5] = (top + 1 < end) ? top[1] : *n;
		_pawesegu_rotate( &rot, movl, movr );
		*low = rot.n[0];
		*mid = rot.n[2];
		*top = rot.n[4];
		rot.n[0] = rot.n[1];
		rot.n[2] = rot.n[3];
		rot.n[4] = rot.n[5];
	}
}

Eventually realised it was impossible to do bit rotation without the copy of the original to reference:

Code:

PAW_QCK pawku* _paweintu__ror_move
	( pawku a, pawku b, pawju shl, pawju shr  )
	{ return (a >> shr) | (b << shl); }
PAW_QCK pawku* _paweintu__ror_loop
(
	pawku *a, pawku const *b,
	pawku const *i, pawku const *end,
	pawju shl, pawju shr
)
{
	for ( ; i < end; *a = _paweintu__ror_move( *b, b, shl, shr ), ++a, ++b, ++i );
	return a;
}
PAW_QCK void _paweintu__ror( pawku *n, pawku const *cpy, pawju have, pawju move )
{
	pawku *d = n;
	pawju shr = move % PAWKD_WIDTH;
	pawju shl = PAWKD_WIDTH - shr;
	pawju jmp = (move / PAWKD_WIDTH) % have;
	pawku const *end = *cpy + have, *s = *end - tmp;
	d  = _paweintu__ror_loop( n, s, s, end - 1, shl, shr );
	*(d++) = _paweintu__ror_move( end - 1, *cpy, shl, shr );
	d  = _paweintu__ror_loop( d, cpy, d, n + have, shl, shr );
}

PAW_FQK void _paweintu_ror( pawku *n, pawju size, pawju move )
	{ _paweintu_ror( n, size / sizeof(pawku), move ); }

When the loop halt to switch to front of the integer, it would need the original value in the front segment which is lost in the destination by the time get to it so the copy is needed to circumvent that