Serialization and Bit Operations CS 2022 Introduction to C Instructor Hussam Abu Libdeh Presented by Renato Paes Leme Cornell University based on slides by Saikat Guha Fall 2009 Lecture 10 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Serialization Sending data between programs Disk Network Pipes Between programs on multiple hosts Different endianness Different architectures Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Binary vs Text Text Binary Compact Easily debugged Easy to encode decode Can be self documenting Faster Arch Endian independent e g IP TCP AIM Serialization and Bit Operations e g HTTP SMTP MSN CS 2022 Fall 2009 Lecture 10 Ok but how What serialization solution to use tpl library c11n library Google protocol buffers Customized solution Which standard to use XML XDR protocol buffer Network protocol standards Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Handling Endianness Decimal 3735928559 Binary 11011110101011011011111011101111 Hex 0xdeadbeef Big Endian 0xde 0xad 0xbe 0xef Little Endian 0xef 0xbe 0xad 0xde Always in big endian form when loaded into the CPU Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Bit Operations AND Mask clear bits a b 11011110101011011011111011101111 00000000000000001111111100000000 0xdeadbeef 0x0000FF00 00000000000000001011111000000000 0x0000be00 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Bit Operations OR Mask sets bits a b 11011110101011011011111011101111 00000000000000000101010100000000 0xdeadbeef 0x00005500 11011110101011011111111111101111 0xdeadFFef Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Bit Operations Left Shift a b 11011110101011011011111011101111 8 0xdeadbeef 8 10101101101111101110111100000000 0xadbeef00 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Bit Operations Right Shift a b 11011110101011011011111011101111 8 0xdeadbeef 8 00000000110111101010110110111110 0x00deadbe 1 1 for unsigned ints only For signed ints the instead of zero padding the top most bit is repeated Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Bit Operations Compliment flips bits a 11011110101011011011111011101111 00100001010100100100000100010000 0xdeadbeef 0x21524110 2 s compliment representation for negative numbers x x 1 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Exercise 1 int htonl int x int b1 b2 b3 b4 y b1 b2 b3 b4 x x x x y b1 b2 b3 b4 return y Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Exercise 2 int htonl int x int y char xs x ys y return y Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Serialization 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 Version IHL Type of Service Total Length Identification Fragment Offset Time to Live Protocol Header Checksum Source Address Destination Address Options Use uint8 t uint16 t uint32 t Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Serialization pragma pack push struct ip ifdef LITTLE ENDIAN uint8 t ihl 4 ver 4 else uint8 t ver 4 ihl 4 endif uint8 t tos uint16 t len uint16 t iid uint16 t off uint8 t ttl uint8 t prt uint16 t csm uint32 t src uint32 t dst char opt 40 pragma pack pop Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Serialization void foo void struct ip ip1 ip2 ip1 struct ip malloc sizeof struct ip ip2 struct ip malloc sizeof struct ip ip1 ver 4 ip1 protocol 6 ip1 len htonl 40 memcpy ip2 ip1 sizeof struct ip printf d d ip2 ver ntohl ip2 len Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Serialization Use structures for data types Copy data in one go memcpy dst src numbytes Use standard big endianness for multi byte variables NEVER serialize pointer values Why Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Tricks with bits How to iterate over all sets S 0 1 2 k 1 There are 2k such sets I just need one for to do that Think of a number 0 0 2k in binary It represents a subset of S 1 i S then we Given a subset S let ai 0 i S Pk 1 i ai 2 represent S by i 0 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Tricks with bits How to iterate over all sets S 1 n int S for S 0 S 1 k S process subset S Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Set Operations Given two sets A and B represented as binary strings Union A B Intersection A B Single element set 1 1 i Testing i A A 1 i 0 Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Set Operations Given two sets A and B represented as binary strings Adding element i to A A A 1 i Removing element i from A A A 1 i Toggle element i in A A A 1 i Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Set Operations Given S a string representation of a set how to iterate over all its subsets T S int T for T S T 0 T T 1 S process subset T Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Set Operations More complicated exercise how to iterate over all subsets of 1 n of size k int s 1 k 1 while s 1 N do stuff with s int lo s s 1 int lz s lo s s lz s lz 1 s lz lo 2 1 Serialization and Bit Operations lowest one bit lowest zero bit above lo add lz to the set reset bits below lz put back right number of bits at end CS 2022 Fall 2009 Lecture 10 Source of bit tricks A bit of fun fun with bits http www topcoder com tc module Static d1 tutorials d2 bitManipulation Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10 Other iteration exercises 1 Write a code that iterates over 0 n 1 k i e all k uples t1 tk where 0 ti n 2 Write a code that iterates over 0 n 1 k i e all k uples t1 tk where 0 ti n and t1 t2 tk 3 Write a code that iterates over all the permutations of 1 n and writes them on the screen Serialization and Bit Operations CS 2022 Fall 2009 Lecture 10