bit_scan_test.c

/* $Id$
 * 
 * test bit_scan operations from bit_scan.h
 *  (both for correctness  and speed)
 * 
 * Copyright (C) 2007 iptelorg GmbH
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
/* 
 * Example gcc command line:
 *  gcc -O9 -Wall -DCC_GCC_LIKE_ASM  -D__CPU_x86 bit_scan_test.c ../bit_scan.c
 *      -o bit_scan_test
 *
 * History:
 * --------
 *  2007-06-23  created by andrei
 */


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


#define BIT_SCAN_DEBRUIJN
#define BIT_SCAN_BRANCH
#define BIT_SCAN_SLOW

#include "../bit_scan.h"
#ifdef NO_PROFILE
#define profile_init(x,y)  do{}while(0)
#define profile_start(x)  do{}while(0)
#define profile_end(x)  do{}while(0)
#define PROFILE_PRINT(x) do{}while(0)
#else
#include "profile.h"
#endif

#define CHECK(txt, v1, val, f, pd) \
        do{ \
                unsigned long long ret; \
                profile_start(pd); \
                ret=(unsigned long long)f(val); \
                profile_end(pd); \
                if ((unsigned long long)v1!=ret){ \
                        fprintf(stderr, "ERROR:" #f ": %s, expected %llx (%llx), got"\
                                        " %llx\n", \
                                        (txt), (unsigned long long)v1, \
                                        (unsigned long long)val, ret); \
                        exit(-1); \
                } \
        }while(0)

#ifndef PROFILE_PRINT
#define PROFILE_PRINT(pd) \
        do{ \
                printf("profile: %s (%ld/%ld) total %llu max %llu average %llu\n", \
                                (pd)->name,  (pd)->entries, (pd)->exits, \
                                (pd)->total_cycles,  (pd)->max_cycles, \
                                (pd)->entries? \
                                (pd)->total_cycles/(unsigned long long)(pd)->entries:0ULL ); \
        }while(0)
#endif

int main(int argc, char** argv)
{
        int r;
        unsigned int v;
        unsigned long long ll;
        int i;
#ifndef NO_PROFILE
        struct profile_data pdf1, pdf2, pdf4, pdf5, pdf6, pdf8;
        struct profile_data pdl1, pdl2, pdl4, pdl5, pdl6, pdl8;
#ifdef HAS_BIT_SCAN_ASM
        struct profile_data pdf3, pdf7, pdl3, pdl7;
#endif
        struct profile_data pdf_32, pdf_64, pdl_32, pdl_64;
        struct profile_data pdf_long, pdl_long;
#endif /* NO_PROFILE */
        
        profile_init(&pdf1, "first_debruijn32");
        profile_init(&pdf2, "first_slow32");
#ifdef HAS_BIT_SCAN_ASM
        profile_init(&pdf3, "first_asm32");
#endif
        profile_init(&pdf4, "first_br32");
        profile_init(&pdf5, "first_debruijn64");
        profile_init(&pdf6, "first_slow64");
#ifdef HAS_BIT_SCAN_ASM
        profile_init(&pdf7, "first_asm64");
#endif
        profile_init(&pdf8, "first_br64");
        profile_init(&pdl1, "last_debruijn32");
        profile_init(&pdl2, "last_slow32");
#ifdef HAS_BIT_SCAN_ASM
        profile_init(&pdl3, "last_asm32");
#endif
        profile_init(&pdl4, "last_br32");
        profile_init(&pdl5, "last_debruijn64");
        profile_init(&pdl6, "last_slow64");
#ifdef HAS_BIT_SCAN_ASM
        profile_init(&pdl7, "last_asm64");
#endif
        profile_init(&pdl8, "last_br64");
        
        profile_init(&pdf_32, "scan_forward32");
        profile_init(&pdf_64, "scan_forward64");
        profile_init(&pdl_32, "scan_reverse32");
        profile_init(&pdl_64, "scan_reverse64");
        profile_init(&pdf_long, "scan_forward_l");
        profile_init(&pdl_long, "scan_reverse_l");


        for (i=0; i<100; i++){
        for (r=0; r<32; r++){
                v=(1U<<r);
                CHECK("first debruijn 32bit", r, v, bit_scan_forward_debruijn32, &pdf1);
                CHECK("first slow 32bit", r, v, bit_scan_forward_slow32, &pdf2);
#ifdef HAS_BIT_SCAN_ASM
                CHECK("first asm 32bit", r, v, bit_scan_forward_asm32, &pdf3);
#endif
                CHECK("first br 32bit", r, v, bit_scan_forward_br32, &pdf4);
                CHECK("scan_forward32", r, v, bit_scan_forward32, &pdf_32);
                if (sizeof(long)<=4){
                        CHECK("scan_forward_l", r, v, bit_scan_forward, &pdf_long);
                }
                v+=(v-1);
                CHECK("last debruijn 32bit", r, v, bit_scan_reverse_debruijn32, &pdl1);
                CHECK("last slow 32bit", r, v, bit_scan_reverse_slow32, &pdl2);
#ifdef HAS_BIT_SCAN_ASM
                CHECK("last asm 32bit", r, v, bit_scan_reverse_asm32, &pdl3);
#endif
                CHECK("last br 32bit", r, v, bit_scan_reverse_br32, &pdl4);
                CHECK("scan_reverse32", r, v, bit_scan_reverse32, &pdl_32);
                if (sizeof(long)<=4){
                        CHECK("scan_reverse_l", r, v, bit_scan_reverse, &pdl_long);
                }
        }
        for (r=0; r<64; r++){
                ll=(1ULL<<r);
                CHECK("first debruijn 64bit", r, ll, bit_scan_forward_debruijn64, &pdf5);
                CHECK("first slow 64bit", r, ll, bit_scan_forward_slow64, &pdf6);
#ifdef HAS_BIT_SCAN_ASM
                CHECK("first asm 64bit", r, ll, bit_scan_forward_asm64, &pdf7);
#endif
                CHECK("first br 64bit", r, ll, bit_scan_forward_br64, &pdf8);
                CHECK("scan_forward64", r, ll, bit_scan_forward64, &pdf_64);
                if (sizeof(long)>4){
                        CHECK("scan_forward_l", r, ll, bit_scan_forward, &pdf_long);
                }
                ll+=ll-1;
                CHECK("last debruijn 64bit", r, ll, bit_scan_reverse_debruijn64, &pdl5);
                CHECK("last slow 64bit", r, ll, bit_scan_reverse_slow64, &pdl6);
#ifdef HAS_BIT_SCAN_ASM
                CHECK("last asm 64bit", r, ll, bit_scan_reverse_asm64, &pdl7);
#endif
                CHECK("last br 64bit", r, ll, bit_scan_reverse_br64, &pdl8);
                CHECK("scan_reverse64", r, ll, bit_scan_reverse64, &pdl_64);
                if (sizeof(long)>4){
                        CHECK("scan_reverse_l", r, ll, bit_scan_reverse, &pdl_long);
                }
        }
        }

        PROFILE_PRINT(&pdf1);
        PROFILE_PRINT(&pdf2);
#ifdef HAS_BIT_SCAN_ASM
        PROFILE_PRINT(&pdf3);
#endif
        PROFILE_PRINT(&pdf4);
        PROFILE_PRINT(&pdl1);
        PROFILE_PRINT(&pdl2);
#ifdef HAS_BIT_SCAN_ASM
        PROFILE_PRINT(&pdl3);
#endif
        PROFILE_PRINT(&pdl4);
        PROFILE_PRINT(&pdf5);
        PROFILE_PRINT(&pdf6);
#ifdef HAS_BIT_SCAN_ASM
        PROFILE_PRINT(&pdf7);
#endif
        PROFILE_PRINT(&pdf8);
        PROFILE_PRINT(&pdl5);
        PROFILE_PRINT(&pdl6);
#ifdef HAS_BIT_SCAN_ASM
        PROFILE_PRINT(&pdl7);
#endif
        PROFILE_PRINT(&pdl8);
        
        PROFILE_PRINT(&pdf_32);
        PROFILE_PRINT(&pdf_64);
        PROFILE_PRINT(&pdf_long);
        PROFILE_PRINT(&pdl_32);
        PROFILE_PRINT(&pdl_64);
        PROFILE_PRINT(&pdl_long);
        return 0;
}