Bits, Bytes, and Integers August 28, 2008Binary RepresentationsEncoding Byte ValuesByte-Oriented Memory OrganizationMachine WordsWord-Oriented Memory OrganizationData RepresentationsByte OrderingByte Ordering ExampleReading Byte-Reversed ListingsExamining Data Representationsshow_bytes Execution ExampleRepresenting IntegersRepresenting PointersRepresenting StringsBoolean AlgebraApplication of Boolean AlgebraGeneral Boolean AlgebrasRepresenting & Manipulating SetsBit-Level Operations in CContrast: Logic Operations in CShift OperationsInteger C PuzzlesEncoding IntegersEncoding Example (Cont.)Numeric RangesValues for Different Word SizesUnsigned & Signed Numeric ValuesMapping Between Signed & UnsignedMapping Signed UnsignedSlide 31Relation between Signed & UnsignedSigned vs. Unsigned in CCasting SurprisesExplanation of Casting SurprisesCode Security Example #1Typical UsageMalicious UsageSign ExtensionSign Extension ExampleWhy Should I Use Unsigned?Complement & IncrementComp. & Incr. ExamplesUnsigned AdditionVisualizing Integer AdditionVisualizing Unsigned AdditionMathematical PropertiesTwo’s Complement AdditionTAdd OverflowVisualizing 2’s Comp. 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 CodeProperties of Unsigned ArithmeticProperties of Two’s Comp. ArithmeticInteger C Puzzles RevisitedBits, Bytes, and IntegersAugust 28, 2008Bits, Bytes, and IntegersAugust 28, 2008TopicsTopicsRepresenting information as bitsBit-level manipulationsBoolean algebraExpressing in CRepresentations of IntegersBasic properties and operationsImplications for C15-213 F ‘08class02.ppt15-213“The Class That Gives CMU Its Zip!”– 2 –15-213, F ‘08Binary RepresentationsBinary RepresentationsBase 2 Number RepresentationBase 2 Number RepresentationRepresent 1521310 as 111011011011012Represent 1.2010 as 1.0011001100110011[0011]…2Represent 1.5213 X 104 as 1.11011011011012 X 213Electronic ImplementationElectronic ImplementationEasy to store with bistable elementsReliably transmitted on noisy and inaccurate wires 0.0V0.5V2.8V3.3V0 1 0– 3 –15-213, F ‘08Encoding Byte ValuesEncoding Byte ValuesByte = 8 bitsByte = 8 bitsBinary 000000002 to 111111112Decimal: 010to 25510First digit must not be 0 in CHexadecimal 0016 to FF16Base 16 number representationUse characters ‘0’ to ‘9’ and ‘A’ to ‘F’Write FA1D37B16 in C as 0xFA1D37B»Or 0xfa1d37b0 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 1111HexDecimalBinary– 4 –15-213, F ‘08Byte-Oriented Memory OrganizationByte-Oriented Memory OrganizationPrograms Refer to Virtual AddressesPrograms 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 AllocationCompiler + Run-Time System Control AllocationWhere different program objects should be storedAll allocation within single virtual address space• • •00•••0FF•••F– 5 –15-213, F ‘08Machine WordsMachine WordsMachine Has “Word Size”Machine 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 bytes– 6 –15-213, F ‘08Word-Oriented Memory OrganizationWord-Oriented Memory OrganizationAddresses Specify Byte Addresses Specify Byte LocationsLocationsAddress 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 =??000000040008001200000008– 7 –15-213, F ‘08Data RepresentationsData RepresentationsSizes of C Objects (in Bytes)Sizes of C Objects (in Bytes)C Data Type Typical 32-bit Intel 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/16char * 4 4 8»Or any other pointer– 8 –15-213, F ‘08Byte OrderingByte OrderingHow should bytes within multi-byte word be ordered in How should bytes within multi-byte word be ordered in memory?memory?ConventionsConventionsBig Endian: Sun, PPC Mac, InternetLeast significant byte has highest addressLittle Endian: x86Least significant byte has lowest address– 9 –15-213, F ‘08Byte Ordering ExampleByte Ordering ExampleBig EndianBig EndianLeast significant byte has highest addressLittle EndianLittle EndianLeast significant byte has lowest addressExampleExampleVariable 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 01– 10 –15-213, F ‘08Reading Byte-Reversed ListingsReading Byte-Reversed ListingsDisassemblyDisassemblyText representation of binary machine codeGenerated by program that reads the machine codeExample FragmentExample Fragment 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)Deciphering NumbersDeciphering NumbersValue: 0x12abPad to 32 bits: 0x000012abSplit into bytes: 00 00 12 abReverse: ab 12 00 00– 11 –15-213, F ‘08Examining Data RepresentationsExamining Data RepresentationsCode to Print Byte Representation of DataCode to Print Byte Representation of DataCasting pointer to unsigned char * creates byte arraytypedef unsigned
View Full Document