datalab

Data lab how to

video

How to test your result

1. first of all, make your files
2. ./btest will test whether your results are correct or not, but not the process
3. ./dlc bits.c will check whether your codes are following the rules/
4. ./driver.pl will finally score your codes.
5. for more information, ./binaryname --help

Utilities

fshow and ishow will give you some useful informatio.

Tips

• Be careful of operator precedence, use parentheses instead of your memory
• take advantages of special operators and values like !,0,Tmin

Data lab

Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.

/* 
 * CS:APP Data Lab 
 * 
 * <Please put your name and userid here>
 * 
 * bits.c - Source file with your solutions to the Lab.
 *          This is the file you will hand in to your instructor.
 *
 * WARNING: Do not include the <stdio.h> header; it confuses the dlc
 * compiler. You can still use printf for debugging without including
 * <stdio.h>, although you might get a compiler warning. In general,
 * it's not good practice to ignore compiler warnings, but in this
 * case it's OK.  
 */

#if 0
/*
 * Instructions to Students:
 *
 * STEP 1: Read the following instructions carefully.
 */

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

INTEGER CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
    
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.

 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount
     is less than 0 or greater than 31.


EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

FLOATING POINT CODING RULES

For the problems that require you to implement floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants. You can use any arithmetic,
logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operations (integer, logical,
     or comparison) that you are allowed to use for your implementation
     of the function.  The max operator count is checked by dlc.
     Note that assignment ('=') is not counted; you may use as many of
     these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. Use the BDD checker to formally verify your functions
  5. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies 
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.

/*
 * STEP 2: Modify the following functions according the coding rules.
 * 
 *   IMPORTANT. TO AVOID GRADING SURPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the BDD checker to formally verify that your solutions produce 
 *      the correct answers.
 */


#endif
//1
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
    /* 
     * from boolean algebra, we know that NAND is functional completeness,
     * so it is possible to express ^ by using only ~ and &.
     */
  return ~(~(~x & y) & ~(x & ~y));
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
    /* view minimum two's complement integer in bit level, we can see that it is a bit string 100000...00
     * This value can be generated by simply shifting a constant 1
     */
  return (1 << 31);

}
//2
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
    /* Tmax has a bit representation of 0111...11, this bit pattern is hard to generate with given ops.
     * However, Tmax + 1 = Tmin, we can check whether (x+1) == Tmin
     * I faciliate the property of Tmin that (Tmin + Tmin == 0)
     */
    // original answer : return !( ((x+1) + (x+1)) ^ 0);
    // fail on x = -1
    /* now make use of shift of signed number to generate the bit pattern */
    return  !( ((x+1) + (x+1)) ^ 0) & !!(x+1);
}
/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
    /* Since we only care about the odd numbered bits, we can use a mask to extract them.
     * From the given example, we can see that 0xAA serve as a good mask 10101010.
     * Due to the forbiddenness of big number like 0xAAAAAAAA, I generate it via shifting.
     */
    //ERROR: Test allOddBits(-1[0xffffffff]) failed...
    //original answer :  return !(x ^ ( 0xAA + (0xAA << 8 ) + (0xAA << 16) + (0xAA << 24) ) );
    int mask =  0xAA + (0xAA << 8 ) + (0xAA << 16) + (0xAA << 24) ;
    return !((x & mask) ^ mask);
}
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
    /* This is quite simple by abelian group addition.  */
  return (~x + 1);
}
//3
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
    /* check the bits parts by parts via masking technique */
    int one = !((x & ~0xF) ^ 0x30); 
    int bit4 = (x & 0x8) ;
    int two = ( (bit4>> 3)& !(x & 0x6))|(!bit4);// if the low oreder bits is 1xxx it must be 100x
    return one & two ;
}
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
    /* make use of boolean property and truth table 
     * We can easily implement it by return (x*y + !x*z) 
     * However, multiple is not allowed, so we must simulate one with & operator 
     * During the simulation, we take advantage of modulo addition */
    int flag = !!x;
    int mask = ~(flag + ~0)  ;
    return  (mask & y) +  (~mask & z);
}
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
    /* If x == Tmin, then the function should return true all the time.
     * If x != Tmin, y == Tmin, the return value is always false
     * If x != Tmin, y != Tmin, the expression can equivalent to (-x >= -y) -> (-x + y >= 0)
     */
    //int inversex = ~x + 1;
    //int Tmin = 1 << 31 ;
    //int isxTmin = !(inversex ^ x);
    //int isyTmin = !(y ^ Tmin);
    //int noneg = !(((inversex + y) & (1 << 31)) >> 31 ) ; 
    //return ( isxTmin | (!isxTmin & !isyTmin & noneg)) & !((!isxTmin) & isyTmin) ;
    /*  steal from https://hackmd.io/@siahuat0727/Bkf4Ei0oQ?type=view#isLessOrEqual--gt-924-ops */
    // (x is - && y is +,0) || (x, y have same sign && (y - x) >= 0)
    return ((x >> 31) & !(y >> 31)) | !(((x ^ y) >> 31) | ((y + ~x + 1) >> 31));
    

}
//4
/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
    /* Faciliate the difference between logical right shift and arithmetic right shift.
     * If x < 0 , the most significant bit must be 1
     * If x == 0 , the MSB must be 0, moreover (~x + 1) == 0
     * If x > 0 , then (~x + 1) must < 0
     */
    int inverse = ~x + 1 ;
    int mask = (1 << 31) ;
    // int flag =  (((x & mask) >> 31) & 1) + (((inverse & mask) >> 31) & 1);
    int flag = ~( ( (x & mask) | (inverse & mask) ) >> 31 )   & 1  ;
    //return (~flag) & 1;
    return flag ;

}
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
    /* If x >= 0 , the function just need to return bin(x) + 1 
     * If x < 0 , the function just need to return bin(~x) + 1
     */
    int MSB = (x & (1 << 31)) >> 31 ;
    int absx = ((~x) & MSB) + (x & ~MSB);
    //use bit level binary search to find log_2(x)
    //I steal the solution from https://github.com/jerrylzy/CS33/blob/master/Lab/datalab/bits.c
    //I also come up with this idea, but failed to believe in myself and turn it into codes.
    int bit16 = 0 ;
    int bit8 = 0;
    int bit4 = 0 ;
    int bit2 = 0;
    int bit1 = 0 ;
    int bit0 = 0 ;
    bit16 = !!(absx >> 16) << 4;
    absx = absx >> bit16 ;
    bit8 = !!(absx >> 8) << 3 ;
    absx = absx >> bit8 ;
    bit4 = !!(absx >> 4) << 2 ;
    absx = absx >> bit4 ;
    bit2 = !!(absx >> 2) << 1 ;
    absx = absx >> bit2 ;
    bit1 = !!(absx >> 1) ;
    absx = absx >> bit1 ;
    bit0 = absx ;

    return  bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1;



}
//float
/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
    /*
     * Due to the smooth transition between denormalized and nomoralized number
     * we can just combine exp and frac then shift them together
     * However we still need to extract exponent part to see whether it is NaN
     */
    int MSBsaver  = uf & (1<<31) ;
    int exp = ((0xFF << 23) & uf )>>23 ;
    int fracmask = ~((1 << 31) + (0xFF << 23));
    int frac = uf & fracmask;
    int res = 0;

    if ( exp == 0xFF ){ return uf ; } //first check
    if (exp == 0){ res = (uf << 2)>>1 | MSBsaver ; } //Denormalized 
    else{
    //Normalized
    exp = exp + 1;
    res = MSBsaver | ((exp << 23) + frac );
    }
    //final check
    if ( exp == 0xFF && frac != 0 ){ res = uf; }
    return  res;
}
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
    /* Recall the comparison between int bits and float bits, they share the frac part
     * We still need to extract the exponent part to check whether there is an overflow and
     * the frac part to generate the int
     */

    int MSB = (uf & (1<<31)) >> 31 ;
    int exp = ((0xFF << 23) & uf )>>23 ;
    int fracmask = ~((1 << 31) + (0xFF << 23));
    int frac = uf & fracmask;
    int res = 0x80000000u ;
    int e = 0;

    if (exp != 0xff ){
        if (exp == 0 ) return 0 ;
        e = exp - 127 ;
        if ( e <= 30  && 0 <= e) {
            if (e >= 23 )
            res =  (frac + (1<<23)) << e;
            else {
            res = (frac + (1<<23)) >> (23 - e );
            }

            if (MSB == 1) { res = (~res) + 1; }
            }
            else if (exp - 127 == 31 && frac == 0){
                res  = (1 << 31);
            }
        else if (e < 0) res = 0;
      
    }
    return  res ;
}

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    /* Since IEEE float point have the value (s)*(1.M)*2^(exp - 127) for normalized case
     * we only need to modify the exponent part to (x + 127)
     * For denormalized case, (s)*(0.M) * 2^(1-127),
     * we only need to modify the frac part to 2^(x+126), from a bit prespective 0.00..00100...0
     */
    int exp = 0;
    int frac = 0;

    if (x < -149) return 0;
    if (x > 128 ) return (0xFF << 23) ;
    if ( x >= -126 ){
    exp = x + 127 ;
    }
    else{
    frac =  (1<<23) >> (-(x + 126));
    }
    return (exp << 23) + frac ;

}

Correctness Results	Perf Results
Points	Rating	Errors	Points	Ops	Puzzle
1	1	0	2	8	bitXor
1	1	0	2	1	tmin
1	1	0	2	9	isTmax
2	2	0	2	9	allOddBits
2	2	0	2	2	negate
3	3	0	2	12	isAsciiDigit
3	3	0	2	9	conditional
3	3	0	2	13	isLessOrEqual
4	4	0	2	9	logicalNeg
4	4	0	2	38	howManyBits
4	4	0	2	22	floatScale2
4	4	0	0	34	floatFloat2Int
4	4	0	2	13	floatPower2

Score = 60/62 [36/36 Corr + 24/26 Perf] (179 total operators)

I don’t do a good job.

See people who are really good at bit level programming