CODEWITHSUNDEEP
clinux
Santosh A
Santosh A

Reputation: 5351

Optimized method to check if an integer lies in the given range/bounds check

In c programming to find if any given value lies between the range, if condition is used as below.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define U_LIMIT     100
#define L_LIMIT    -100

int check_num(char *in)
{
    int i = 0;

    if (in[i] == '-' || in[i] == '+') {
        i++;
        if (in[i] == '\0')
            return 0;
    }

    while (i < strlen(in)) {
        if(!isdigit(in[i]))
            return 0;
        i++;
    }
    return 1;
}

int main(int argc, char *argv[])
{
    int i;
    if (argc != 2)
       return 1;

    if (!check_num(argv[1])) {
       printf("Not a digit\n");
       return 1;
    }

    i = atoi(argv[1]);
    if (i < U_LIMIT && i > L_LIMIT)
       printf("Within Range\n");
    else
       printf("Outside Range\n");

    return 0;
}

Sample Output:

./a.out 1    -> Within Range
./a.out 100  -> Outside Range
./a.out -100 -> Outside Range
./a.out -    -> Not a digit
./a.out e    -> Not a digit

My question is that

  1. Can the above program be optimized(for speed) further without loosing out any of the error check conditions?
  2. Is there any other best optimized(for speed) method to solve for the same issue?

Upvotes: 0

Views: 1633

Answers (3)

Jonathon Reinhart
Jonathon Reinhart

Reputation: 137418

There's no need to check the user input, and then parse it. Just use sscanf to accomplish both at once:

#include <stdio.h>

#define U_LIMIT     100
#define L_LIMIT    -100

int main(int argc, char *argv[])
{
    int i;

    if (argc != 2) {
        printf("Missing argument\n");
        return 1;
    }

    /* ALWAYS check the return value from scanf() and friends!
     * It returns the number of items in your format string successfully
     * assigned to. Make sure it matches the number of values you're
     * expecting, (one in this case).
     */
    if (sscanf(argv[1], "%d", &i) != 1) {
        printf("Invalid number\n");
        return 1;
    }

    /* Doesn't get any simpler than an if statement */
    if (i < U_LIMIT && i > L_LIMIT)
       printf("Within Range\n");
    else
       printf("Outside Range\n");

    return 0;
}

Also, don't try to do crazy optimizations this early in the game. Focus on writing clean, concise code, and let the optimizing compiler take care of the rest for you.

At -O3 optimization level, GCC produces the following assembly for main(). I kept just the interesting part about the integer comparison.

GCC command line: gcc -Wall -Werror -O3 -g test.c

Objdump command line: objdump -d -Mintel -S a.out

if (i < U_LIMIT && i > L_LIMIT)
  4004e5:   mov    eax,DWORD PTR [rsp]
  4004e8:   add    eax,0x63
  4004eb:   cmp    eax,0xc6
  4004f0:   jbe    400500 <main+0x50>

Note what the compiler did for you. Instead of making two comparisons, it first added 0x63 (99) to i, then, compared that value to 0xC6 (198). This is equivalent to something like:

if ((unsigned int)(i + 99) <= 198)

This way, only one conditional branch was necessary. The cool part is that it does an unsigned comparison. If i was less than -100, then (i + 99) would still be negative, and interpreted as an unsigned integer is 0xfffffed3 (a really big number) which is not <= 198.

And the best part? You didn't even need to think about it!

Upvotes: 2

akira
akira

Reputation: 6117

Option strtol()

You might want to use just strtol(3):

long int strtol(const char *nptr, char **endptr, int base);

The strtol() function converts the initial part of the string in 
nptr to a long integer value according to the given base, which 
must be between 2 and 36 inclusive, or be the special value 0.

Furthermore: you will get a return value if the input data overflows or underflows.

Furthermore: the function will place the endptr to the first 'invalid' character.

char*     in = "123a";
size_t   len = strlen(in);
char*    end = NULL;
long int out = strtol(in, &end, 10);

if (out == LONG_MIN || out == LONG_MAX) {
    // underflow || overflow
} else if (in + len < end) {
    // invalid chars while parsing
} else {
    // ok
}

Option sscanf()

The standard alternative is to use sscanf() which is ok in general but might be a bottleneck when you need to parse A LOT of integers (reparsing the format-string is an issue).

Option rollyourown()

Since you roll your own check already you might as well do the parsing yourself (taken from scan_ulong.c of qmail):

unsigned int scan_ulong(const char *s, unsigned long *u) {
    unsigned int pos = 0;
    unsigned long result = 0;
    unsigned long c;
    while ((c = (unsigned long) (unsigned char) (s[pos] - '0')) < 10) {
        result = result * 10 + c;
        ++pos;
    }

    if (u) {
        *u = result;
    }
    return pos;
}

This piece is the equivalent of your isdigit() code but also parses the number at the same time. If parsing numbers is a speed issue for your project, consider option strtol() (depends a bit on which compiler / platform you use) or the scan_ulong() variant, otherwise just stick with sscanf().

Upvotes: 1

Gopi
Gopi

Reputation: 19864

while (i < strlen(in))

Since your question asks about time optimization then here is a part which you improve on

int n =strlen(in);

while(i<n){

by doing this strlen() is not calculated in each iteration which is time consuming. Rest of the code should be fine as you are using if() to check the bounds which is simpler and best.

Upvotes: 2

Related Questions