Thread: Wierd bug in bignum left shift function

  1. #31
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Left rotate:
    Code:
    int __alu_rol( alu_t *alu, int num, size_t by )
    {
    	alu_reg_t *N, *T;
    	alu_bit_t n = {0}, v;
    	int ret = _alu_check1( alu, num ), tmp = -1;
    	
    	if ( ret != 0 )
    	{
    		alu_error( ret );
    		return ret;
    	}
    	
    	ret = alu_get_reg( alu, &tmp );
    	
    	if ( ret != 0 )
    	{
    		alu_error( ret );
    		return ret;
    	}
    	
    	N = alu->regv + num;
    	T = alu->regv + tmp;
    	
    	memcpy( T->part, N->part, alu->buff.perN );
    	memset( N->part, 0, alu->buff.perN );
    	
    	T->upto = alu_bit_set_bit( T->part, N->upto.b );
    	T->last = alu_bit_set_bit( T->part, N->last.b );
    	T->init = alu_bit_set_bit( T->part, N->init.b );
    	
    	n = N->upto;
    	by %= n.b;
    	v = alu_bit_set_bit( T->part, n.b - by );
    	
    	while ( v.b > N->init.b )
    	{
    		v = alu_bit_dec( v );
    		n = alu_bit_dec( n );
    		
    		if ( *(v.S) & v.B )
    			*(n.S) |= n.B;
    	}
    	
    	v = T->upto;
    	while ( n.b > N->init.b )
    	{
    		v = alu_bit_dec( v );
    		n = alu_bit_dec( n );
    		
    		if ( *(v.S) & v.B )
    			*(n.S) |= n.B;
    	}
    	
    	(void)alu_rem_reg( alu, tmp );
    	
    	return 0;
    }

  2. #32
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    What REG->upto, REG->last & REG->init hold
    Code:
    typedef struct alu_bit {
    	size_t s, b, p; alu_seg_t *S, B;
    } alu_bit_t;
    s represents segment number (used as (alu_seg_t*)(REG->part) + s)
    b represents bit number (defined as s = b / ALU_SEG_WIDTH)
    p represents bit position (defined as p = b % ALU_SEG_WIDTH)
    S is a segment pointer (defined as S = (alu_seg_t*)(REG->part) + s)
    B is the bit that working with (defined as B = 1u << p)

    Edit: Thought it might be easier for peops to understand with the actual function:
    Code:
    struct alu_bit alu_bit_set_bit
    (
    	alu_seg_t *init,
    	size_t bit
    )
    {
    	alu_bit_t pos = {0};
    	pos.b = bit;
    	pos.p = bit % ALU_SEG_WIDTH;
    	pos.s = bit / ALU_SEG_WIDTH;
    	pos.S = init + pos.s;
    	pos.B = 1u << pos.p;
    	return pos;
    }
    Last edited by awsdert; 07-31-2020 at 05:08 AM.

  3. #33
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Quote Originally Posted by awsdert View Post
    What REG->upto, REG->last & REG->init hold
    Code:
    typedef struct alu_bit {
    	size_t s, b, p; alu_seg_t *S, B;
    } alu_bit_t;
    s represents segment number (used as (alu_seg_t*)(REG->part) + s)
    b represents bit number (defined as s = b / ALU_SEG_WIDTH)
    p represents bit position (defined as p = b % ALU_SEG_WIDTH)
    S is a segment pointer (defined as S = (alu_seg_t*)(REG->part) + s)
    B is the bit that working with (defined as B = 1u << p)

    Edit: Thought it might be easier for peops to understand with the actual function:
    Code:
    struct alu_bit alu_bit_set_bit
    (
    	alu_seg_t *init,
    	size_t bit
    )
    {
    	alu_bit_t pos = {0};
    	pos.b = bit;
    	pos.p = bit % ALU_SEG_WIDTH;
    	pos.s = bit / ALU_SEG_WIDTH;
    	pos.S = init + pos.s;
    	pos.B = 1u << pos.p;
    	return pos;
    }
    Turned out the problem was this very function, where this:
    Code:
    pos.B = 1u << pos.p
    should've been this:
    Code:
    pos.B = 1llu << pos.p
    or with my newly made macro, this:
    Code:
    pos.B = ALU_SEG_C(1) << pos.p
    After changing that the results came out correct, moving on to new but related question, what is supposed to happen when a rotate involves a greater number of bits than the integer uses? In my function I've just gone with pretending it was rotated that many times and just used the remaining bits after dividing the amount by the register width but what is actually supposed to happen?

  4. #34
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Quote Originally Posted by laserlight View Post
    This is a very good opportunity to start though: you're writing a self-contained library such that you don't have to worry about things like mocking a database or a server. Plus it'll look good on your resume if you want to join a software engineering team rather than work solo or as a hobbyist (but arguably solo developers might benefit even more from automated unit testing since they don't have the benefit of peer review).


    Yeah, I guessed as much, and did the same because I've been programming in Python lately, but the reserved name rules for Python are different from C. Unless you're going for a post-processing amalgamation approach like for SQLite (so you end up with one big source file regardless of how many you start with), you should declare your internal functions static: besides the benefit of avoiding name collision, it'll make it clear that they are internal regardless of naming convention.
    I tried adding that static to single function in the header, compiler complained it was undefined then so I #if 0'd the original and copied it's code to the header, compiler is now saying it's unused in certain cases, why does it need to report that?
    Code:
    MAKECMDGOALS=rebuild
    make -f main.mak rebuild
    rm -f *.AppImage *.exe *.so *.dll *.o *.obj
    cc -fPIC -shared -Wall -Wextra -o test.o -c test.c
    In file included from test.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_bit.o -c alu_bit.c
    In file included from alu_bit.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_main.o -c alu_main.c
    cc -fPIC -shared -Wall -Wextra -o alu_math.o -c alu_math.c
    cc -fPIC -shared -Wall -Wextra -o alu_mem.o -c alu_mem.c
    In file included from alu_mem.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_vec.o -c alu_vec.c
    In file included from alu_vec.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -o libalu.so alu_bit.o alu_main.o alu_math.o alu_mem.o alu_vec.o
    cc -fPIE -L . -l alu -o alu.AppImage test.o -Wl,-rpath=./
    Compilation finished successfully.

  5. #35
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by awsdert
    I tried adding that static to single function in the header
    That usually doesn't make sense: the point of using the static keyword is to give the function name internal linkage. If you declare it in a header, then you're saying that in every separate source file that includes the header, there is a function that is declared like this, but is somehow unique to that particular source file.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #36
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,733
    Quote Originally Posted by awsdert View Post
    I tried adding that static to single function in the header, compiler complained it was undefined then so I #if 0'd the original and copied it's code to the header, compiler is now saying it's unused in certain cases, why does it need to report that?
    Code:
    MAKECMDGOALS=rebuild
    make -f main.mak rebuild
    rm -f *.AppImage *.exe *.so *.dll *.o *.obj
    cc -fPIC -shared -Wall -Wextra -o test.o -c test.c
    In file included from test.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_bit.o -c alu_bit.c
    In file included from alu_bit.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_main.o -c alu_main.c
    cc -fPIC -shared -Wall -Wextra -o alu_math.o -c alu_math.c
    cc -fPIC -shared -Wall -Wextra -o alu_mem.o -c alu_mem.c
    In file included from alu_mem.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -Wall -Wextra -o alu_vec.o -c alu_vec.c
    In file included from alu_vec.c:1:
    alu.h:91:23: warning: ‘alu_bit_set_bit’ defined but not used [-Wunused-function]
       91 | static struct alu_bit alu_bit_set_bit
          |                       ^~~~~~~~~~~~~~~
    cc -fPIC -shared -o libalu.so alu_bit.o alu_main.o alu_math.o alu_mem.o alu_vec.o
    cc -fPIE -L . -l alu -o alu.AppImage test.o -Wl,-rpath=./
    Compilation finished successfully.
    Judging by what I read on a stack overflow thread it seems unsuitable for this situation since while it's not recommended to use internal functions of a library there are use case scenarios, for example someone is calculating PI, fiddling with wrapper structs and functions creates overhead and they want to minimize it, they would look for functions unlikely to change (in this case all of them once I have signed, unsigned and floating math builtin - which is when I'll mark it stable and recommend it as a download for big math), in this case they know they do not need to check for 0 at any point because the division is built to clamp it the same way a human would do so, instead of infinitely trying to reduce the remainder it just treats the original number as the remainder and 0 as the number of reductions applied, any other suggestions to make instead?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Left and right shift operators
    By Eclipse07 in forum C Programming
    Replies: 4
    Last Post: 12-15-2019, 08:28 PM
  2. Bignum math: right shift
    By awsdert in forum C Programming
    Replies: 1
    Last Post: 11-21-2019, 05:13 AM
  3. c bit shift left and right
    By ssm in forum C Programming
    Replies: 8
    Last Post: 03-01-2016, 02:09 PM
  4. Shift Left, Shift Right Question
    By congi in forum C Programming
    Replies: 1
    Last Post: 01-28-2015, 10:45 AM
  5. Left Shift
    By vb.bajpai in forum C Programming
    Replies: 4
    Last Post: 06-17-2007, 11:15 AM

Tags for this Thread