목차
아래의 내용들은 시스템 프로그래밍(CS230; CSAPP)를 수강할 때 lab session을 진행하고 통과된 코드를 모아두었습니다. 특히 기본적으로 CMU에서 제공하는 datalab 자료 에서 구현하라고 한 함수들과 각 대학에서 주는 과제들을 통합했습니다. 모을 수 있는 함수들은 모두 모았으니 이 글 하나로도 datalab을 정복하실 수 있을 것입니다.
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part1
bitXor, bitAnd, bitNor, bitOr
/getByte, reverseBytes, logicalShift
/Tmin, Tmax, negate, sm2tc, tc2sm
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part2
bitMask, thirdBits, leastBitPos, replaceByte, copyLSB, rotateRight, rotateLeft
/isTmin, isTmax
/isPositive, isNonNegative, isNegative, isNonZero
/isLessOrEqual, isNotEqual, isPower2
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part3
logicalNeg, bang, conditional, isAscii
/allOddBits, allEvenBits, anyOddBit, anyEvenBit, byteSwap, bitParity, bitCount, countOneBits, greatestBitPos, howManyBits, leftBitCount, countPattern
/addOk, subOk, subOverflowFree, isLessOrEqual, absVal
1. 기초 비트 연산 (Basic Bit Operations)
a. bitXor (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) {
return ~(~x&~y) & ~(x&y);
}
b. bitAnd (1)
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~(~x | ~y);
}
c. bitNor (1)
/*
* bitNor - ~(x|y) using only ~ and &
* Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
* Legal ops: ~ &
* Max ops: 8
* Rating: 1
*/
int bitNor(int x, int y) {
return ~(~(~x & ~y));
}
d. bitOr (1)
/*
* bitOr - x|y using only ~ and &
* Example: bitOr(6, 5) = 7
* Legal ops: ~ &
* Max ops: 8
* Rating: 1
*/
int bitOr(int x, int y) {
return ~( (~x) & (~y) );
}
2. 기초 비트 다루기
a. getByte (2)
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
return (x >> (n << 3)) & 0xFF;
}
b. reverseBytes (3)
/*
* reverseBytes - reverse the bytes of x
* Example: reverseBytes(0x01020304) = 0x04030201
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 3
*/
int reverseBytes(int x) {
int n = 0x00;
n = n | ((x >> 24) & 0xFF);
n = n | ((x >> 16) & 0xFF) << 8;
n = n | ((x >> 8) & 0xFF) << 16;
n = n | (x & 0xFF) << 24;
return n;
}
c. logicalShift (3)
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 1 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int logicalShift(int x, int n) {
return (x >> n) & ~(~0 << (32 + (~n + 1)));
}
3. 기초 2의 보수
a. Tmin (1)
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return (1 << 31);
}
b. Tmax (1)
/*
* TMax - return maximum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmax(void) {
int x = 1;
return ~(1 << 31);
}
c. negate (2)
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
d. sm2tc (4)
/*
* sm2tc - Convert from sign-magnitude to two's complement
* where the MSB is the sign bit
* Example: sm2tc(0x80000005) = -5.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 4
*/
int sm2tc(int x)
{
int sign = x >> 31;
int signDigit = sign << 31;
return (((x ^ sign) | signDigit) + !!(sign));
}
e. tc2sm (4)
/*
* tc2sm - Convert from two's complement to sign-magnitude
* where the MSB is the sign bit
* You can assume that x > TMin
* Example: tc2sm(-5) = 0x80000005.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 4
*/
int tc2sm(int x) {
int sign = x >> 31; // sign mask
int mag = (sign & (~x + 1)) | (~sign & x);
return sign << 31 | mag;
}
아래의 내용들은 시스템 프로그래밍(CS230; CSAPP)를 수강할 때 lab session을 진행하고 통과된 코드를 모아두었습니다. 특히 기본적으로 CMU에서 제공하는 datalab 자료 에서 구현하라고 한 함수들과 각 대학에서 주는 과제들을 통합했습니다. 모을 수 있는 함수들은 모두 모았으니 이 글 하나로도 datalab을 정복하실 수 있을 것입니다.
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part1
bitXor, bitAnd, bitNor, bitOr
/getByte, reverseBytes, logicalShift
/Tmin, Tmax, negate, sm2tc, tc2sm
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part2
bitMask, thirdBits, leastBitPos, replaceByte, copyLSB, rotateRight, rotateLeft
/isTmin, isTmax
/isPositive, isNonNegative, isNegative, isNonZero
/isLessOrEqual, isNotEqual, isPower2
- [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part3
logicalNeg, bang, conditional, isAscii
/allOddBits, allEvenBits, anyOddBit, anyEvenBit, byteSwap, bitParity, bitCount, countOneBits, greatestBitPos, howManyBits, leftBitCount, countPattern
/addOk, subOk, subOverflowFree, isLessOrEqual, absVal
1. 기초 비트 연산 (Basic Bit Operations)
a. bitXor (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) { return ~(~x&~y) & ~(x&y); }
b. bitAnd (1)
/* * bitAnd - x&y using only ~ and | * Example: bitAnd(6, 5) = 4 * Legal ops: ~ | * Max ops: 8 * Rating: 1 */ int bitAnd(int x, int y) { return ~(~x | ~y); }
c. bitNor (1)
/* * bitNor - ~(x|y) using only ~ and & * Example: bitNor(0x6, 0x5) = 0xFFFFFFF8 * Legal ops: ~ & * Max ops: 8 * Rating: 1 */ int bitNor(int x, int y) { return ~(~(~x & ~y)); }
d. bitOr (1)
/* * bitOr - x|y using only ~ and & * Example: bitOr(6, 5) = 7 * Legal ops: ~ & * Max ops: 8 * Rating: 1 */ int bitOr(int x, int y) { return ~( (~x) & (~y) ); }
2. 기초 비트 다루기
a. getByte (2)
/* * getByte - Extract byte n from word x * Bytes numbered from 0 (LSB) to 3 (MSB) * Examples: getByte(0x12345678,1) = 0x56 * Legal ops: ! ~ & ^ | + << >> * Max ops: 6 * Rating: 2 */ int getByte(int x, int n) { return (x >> (n << 3)) & 0xFF; }
b. reverseBytes (3)
/* * reverseBytes - reverse the bytes of x * Example: reverseBytes(0x01020304) = 0x04030201 * Legal ops: ! ~ & ^ | + << >> * Max ops: 25 * Rating: 3 */ int reverseBytes(int x) { int n = 0x00; n = n | ((x >> 24) & 0xFF); n = n | ((x >> 16) & 0xFF) << 8; n = n | ((x >> 8) & 0xFF) << 16; n = n | (x & 0xFF) << 24; return n; }
c. logicalShift (3)
/* * logicalShift - shift x to the right by n, using a logical shift * Can assume that 1 <= n <= 31 * Examples: logicalShift(0x87654321,4) = 0x08765432 * Legal ops: ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ int logicalShift(int x, int n) { return (x >> n) & ~(~0 << (32 + (~n + 1))); }
3. 기초 2의 보수
a. Tmin (1)
/* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ int tmin(void) { return (1 << 31); }
b. Tmax (1)
/* * TMax - return maximum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ int tmax(void) { int x = 1; return ~(1 << 31); }
c. negate (2)
/* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int negate(int x) { return ~x + 1; }
d. sm2tc (4)
/* * sm2tc - Convert from sign-magnitude to two's complement * where the MSB is the sign bit * Example: sm2tc(0x80000005) = -5. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 4 */ int sm2tc(int x) { int sign = x >> 31; int signDigit = sign << 31; return (((x ^ sign) | signDigit) + !!(sign)); }
e. tc2sm (4)
/* * tc2sm - Convert from two's complement to sign-magnitude * where the MSB is the sign bit * You can assume that x > TMin * Example: tc2sm(-5) = 0x80000005. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 4 */ int tc2sm(int x) { int sign = x >> 31; // sign mask int mag = (sign & (~x + 1)) | (~sign & x); return sign << 31 | mag; }