Slide 1Today: Bits, Bytes, and IntegersBinary RepresentationsEncoding Byte ValuesByte-Oriented Memory OrganizationMachine WordsWord-Oriented Memory OrganizationData RepresentationsByte OrderingByte Ordering ExampleReading Byte-Reversed ListingsExamining Data Representationsshow_bytes Execution ExampleRepresenting IntegersRepresenting PointersRepresenting StringsToday: Bits, Bytes, and IntegersBoolean AlgebraApplication of Boolean AlgebraGeneral Boolean AlgebrasRepresenting & Manipulating SetsBit-Level Operations in CContrast: Logic Operations in CShift OperationsToday: Bits, Bytes, and IntegersEncoding IntegersEncoding Example (Cont.)Numeric RangesValues for Different Word SizesUnsigned & Signed Numeric ValuesToday: Bits, Bytes, and IntegersMapping Between Signed & UnsignedMapping Signed UnsignedMapping Signed UnsignedRelation between Signed & UnsignedConversion VisualizedSigned vs. Unsigned in CCasting SurprisesCode Security ExampleTypical UsageMalicious UsageSummary Casting Signed ↔ Unsigned: Basic RulesToday: Bits, Bytes, and IntegersSign ExtensionSign Extension ExampleSummary: Expanding, Truncating: Basic RulesToday: Bits, Bytes, and IntegersNegation: Complement & IncrementComplement & Increment ExamplesUnsigned AdditionVisualizing (Mathematical) Integer AdditionVisualizing Unsigned AdditionMathematical PropertiesTwo’s Complement AdditionTAdd OverflowVisualizing 2’s Complement AdditionCharacterizing TAddMathematical Properties of TAddMultiplicationUnsigned Multiplication in CCode Security Example #2XDR CodeXDR VulnerabilitySigned Multiplication in CPower-of-2 Multiply with ShiftCompiled Multiplication CodeUnsigned Power-of-2 Divide with ShiftCompiled Unsigned Division CodeSigned Power-of-2 Divide with ShiftCorrect Power-of-2 DivideCorrect Power-of-2 Divide (Cont.)Compiled Signed Division CodeArithmetic: Basic RulesArithmetic: Basic RulesToday: IntegersProperties of Unsigned ArithmeticProperties of Two’s Comp. ArithmeticWhy Should I Use Unsigned?Integer C PuzzlesCarnegie Mellon1Bits, Bytes, and Integers15-213: Introduction to Computer Systems2nd Lecture, Aug. 26, 2010Instructors: Randy Bryant and Dave O’HallaronCarnegie Mellon2Today: Bits, Bytes, and IntegersRepresenting information as bitsBit-level manipulationsIntegersRepresentation: unsigned and signedConversion, castingExpanding, truncatingAddition, negation, multiplication, shiftingSummaryCarnegie Mellon3Binary Representations0.0V0.5V2.8V3.3V0 1 0Carnegie Mellon4Encoding Byte ValuesByte = 8 bitsBinary 000000002 to 111111112Decimal: 010 to 25510Hexadecimal 0016 to FF16Base 16 number representationUse characters ‘0’ to ‘9’ and ‘A’ to ‘F’Write FA1D37B16 in C as–0xFA1D37B–0xfa1d37b 0 0 00001 1 00012 2 00103 3 00114 4 01005 5 01016 6 01107 7 01118 8 10009 9 1001A 10 1010B 11 1011C 12 1100D 13 1101E 14 1110F 15 1111HexDecimalBinaryCarnegie Mellon5Byte-Oriented Memory OrganizationPrograms Refer to Virtual AddressesConceptually very large array of bytesActually implemented with hierarchy of different memory typesSystem provides address space private to particular “process”Program being executedProgram can clobber its own data, but not that of othersCompiler + Run-Time System Control AllocationWhere different program objects should be storedAll allocation within single virtual address space• • •00•••0FF•••FCarnegie Mellon6Machine WordsMachine Has “Word Size”Nominal size of integer-valued dataIncluding addressesMost current machines use 32 bits (4 bytes) wordsLimits addresses to 4GBBecoming too small for memory-intensive applicationsHigh-end systems use 64 bits (8 bytes) wordsPotential address space ≈ 1.8 X 1019 bytesx86-64 machines support 48-bit addresses: 256 TerabytesMachines support multiple data formatsFractions or multiples of word sizeAlways integral number of bytesCarnegie Mellon7Word-Oriented Memory OrganizationAddresses Specify Byte LocationsAddress of first byte in wordAddresses of successive words differ by 4 (32-bit) or 8 (64-bit)00000001000200030004000500060007000800090010001132-bitWordsBytes Addr.001200130014001564-bitWordsAddr =??Addr =??Addr =??Addr =??Addr =??Addr =??000000040008001200000008Carnegie Mellon8Data RepresentationsC Data TypeTypical 32-bitIntel IA32 x86-64char 1 1 1short 2 2 2int 4 4 4long 4 4 8long long 8 8 8float 4 4 4double 8 8 8long double 8 10/12 10/16pointer 4 4 8Carnegie Mellon9Byte OrderingHow should bytes within a multi-byte word be ordered in memory?ConventionsBig Endian: Sun, PPC Mac, InternetLeast significant byte has highest addressLittle Endian: x86Least significant byte has lowest addressCarnegie Mellon10Byte Ordering ExampleBig EndianLeast significant byte has highest addressLittle EndianLeast significant byte has lowest addressExampleVariable x has 4-byte representation 0x01234567Address given by &x is 0x1000x100 0x101 0x102 0x10301 23 45 670x100 0x101 0x102 0x10367 45 23 01Big EndianLittle Endian01 23 45 6767 45 23 01Carnegie Mellon11 Address Instruction Code Assembly Rendition 8048365: 5b pop %ebx 8048366: 81 c3 ab 12 00 00 add $0x12ab,%ebx 804836c: 83 bb 28 00 00 00 00 cmpl $0x0,0x28(%ebx)Reading Byte-Reversed ListingsDisassemblyText representation of binary machine codeGenerated by program that reads the machine codeExample FragmentDeciphering NumbersValue: 0x12abPad to 32 bits: 0x000012abSplit into bytes: 00 00 12 abReverse: ab 12 00 00Carnegie Mellon12Examining Data RepresentationsCode to Print Byte Representation of DataCasting pointer to unsigned char * creates byte arrayPrintf directives:%p: Print pointer%x: Print Hexadecimaltypedef unsigned char *pointer;void show_bytes(pointer start, int len){ int i; for (i = 0; i < len; i++) printf(”%p\t0x%.2x\n",start+i, start[i]); printf("\n");}typedef unsigned char *pointer;void show_bytes(pointer start, int len){ int i; for (i = 0; i < len; i++) printf(”%p\t0x%.2x\n",start+i, start[i]); printf("\n");}Carnegie Mellon13show_bytes Execution Exampleint a = 15213;printf("int a = 15213;\n");show_bytes((pointer) &a, sizeof(int));int a = 15213;printf("int a = 15213;\n");show_bytes((pointer) &a, sizeof(int));Result (Linux):int a = 15213;0x11ffffcb8 0x6d0x11ffffcb9 0x3b0x11ffffcba 0x000x11ffffcbb 0x00int a = 15213;0x11ffffcb8 0x6d0x11ffffcb9
View Full Document