CODEWITHSUNDEEP
cgcc
Rick
Rick

Reputation: 381

Cannot understand the reason for warning

Please consider the following simple program. When I compile this with compile : gcc -o test test.c I get lots of warning: integer overflow in expression [-Woverflow] warnings. I don't understand why I get these warnings. Note that the variable Q is 31 bits long. I have tried typecasting to uint64_t but without any solution. Interestingly if I remove the #define Q ( (1<<k1) - (1<<k2) + 1 ) and write the numericalvalue of Q as uint64_t Q=2130706433; Then most of the warnings messages are gone but still I get one warning message for m=( m& (k1_minus_one) ) + ( ((m>>k1)<<k2) - (m>>k1) );. If I put the numerical value the code works as expected in spite of the warnings, however with the former #define statement the code does not work. I am using gcc (Ubuntu 6.5.0-2ubuntu1~16.04) 6.5.0 20181026 Can you please tell me what could be the possible source of this problem and possible solutions?

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

//compile : gcc -o test test.c

#define N 1024
#define k1 31
#define k2 24

void mul_mod_large(uint64_t *a, uint64_t *b, uint64_t *c);
void get_arr(uint64_t *a, uint64_t q, uint64_t n);

#define k1_minus_one ( (1<<k1)-1 )
#define Q ( (1<<k1) - (1<<k2) + 1 )
//uint64_t Q=2130706433;

void main(){

}

void mul_mod_large(uint64_t *a, uint64_t *b, uint64_t *c){

    uint64_t i, m;
    for(i=0;i<N;i++){
        m=a[i]*b[i];
        while(m>(2*Q)){
            m=( m& (k1_minus_one) ) + ( ((m>>k1)<<k2) - (m>>k1) );
        }
        c[i]=m;
        if(m>=Q){
            c[i]=m-Q;
        }       
    }
}

Upvotes: 0

Views: 113

Answers (2)

Rick
Rick

Reputation: 381

As many suggested the problem arose due to the default limit of C for #define constants which is int32. So If I put U after the 1's the problem is solved.

#define k1_minus_one ( (1U<<k1)-1 )
#define Q ( (1U<<k1) - (1U<<k2) + 1 )

The above code gives no warnings and runs without errors.

As mentioned in the comments by @Ian Abbott, instead of putting U after 1s writing UINT32_C(1) gives a better and more generic soultion.

Upvotes: 0

Luis Colorado
Luis Colorado

Reputation: 12708

The numbers in a signed 32 bit numer in two's complement varie from -2^31 to 2^31 - 1. You are using the subexpression (1 << 31) which is effectively equivalent to 2^31, which is one plus than the maximum int you can store in your computer. Even if you later subtract one, the partial result (1 << 31) is out of range. Unluckily, signed numbers overflow is Undefined Behaviour in C, so you can get the desired result, or you can receive a completely different behaviour (like crashing or aborting your program). That is the reason for the warning you get. You can get the maximum number in other ways, but the most effective is to simply use 0x7fffffff, or

#include <limits.h>
...
INT_MAX  /* this is very safe :) */

or

(((1 << 30) - 1) << 1) + 1)

(this last example builds 2^31 - 1 by multiplying by 2 the number 2^30 - 1 and adding one to the result, and that's safe)

Upvotes: 1

Related Questions