1# Copyright 2013 The Chromium Authors. All rights reserved. 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5import module as mojom 6 7# This module provides a mechanism for determining the packed order and offsets 8# of a mojom.Struct. 9# 10# ps = pack.PackedStruct(struct) 11# ps.packed_fields will access a list of PackedField objects, each of which 12# will have an offset, a size and a bit (for mojom.BOOLs). 13 14# Size of struct header in bytes: num_bytes [4B] + version [4B]. 15HEADER_SIZE = 8 16 17class PackedField(object): 18 kind_to_size = { 19 mojom.BOOL: 1, 20 mojom.INT8: 1, 21 mojom.UINT8: 1, 22 mojom.INT16: 2, 23 mojom.UINT16: 2, 24 mojom.INT32: 4, 25 mojom.UINT32: 4, 26 mojom.FLOAT: 4, 27 mojom.HANDLE: 4, 28 mojom.MSGPIPE: 4, 29 mojom.SHAREDBUFFER: 4, 30 mojom.DCPIPE: 4, 31 mojom.DPPIPE: 4, 32 mojom.NULLABLE_HANDLE: 4, 33 mojom.NULLABLE_MSGPIPE: 4, 34 mojom.NULLABLE_SHAREDBUFFER: 4, 35 mojom.NULLABLE_DCPIPE: 4, 36 mojom.NULLABLE_DPPIPE: 4, 37 mojom.INT64: 8, 38 mojom.UINT64: 8, 39 mojom.DOUBLE: 8, 40 mojom.STRING: 8, 41 mojom.NULLABLE_STRING: 8 42 } 43 44 @classmethod 45 def GetSizeForKind(cls, kind): 46 if isinstance(kind, (mojom.Array, mojom.Map, mojom.Struct, 47 mojom.Interface, mojom.AssociatedInterface)): 48 return 8 49 if isinstance(kind, mojom.Union): 50 return 16 51 if isinstance(kind, mojom.InterfaceRequest): 52 kind = mojom.MSGPIPE 53 if isinstance(kind, mojom.AssociatedInterfaceRequest): 54 return 4 55 if isinstance(kind, mojom.Enum): 56 # TODO(mpcomplete): what about big enums? 57 return cls.kind_to_size[mojom.INT32] 58 if not kind in cls.kind_to_size: 59 raise Exception("Undefined type: %s. Did you forget to import the file " 60 "containing the definition?" % kind.spec) 61 return cls.kind_to_size[kind] 62 63 @classmethod 64 def GetAlignmentForKind(cls, kind): 65 if isinstance(kind, (mojom.Interface, mojom.AssociatedInterface)): 66 return 4 67 if isinstance(kind, mojom.Union): 68 return 8 69 return cls.GetSizeForKind(kind) 70 71 def __init__(self, field, index, ordinal): 72 """ 73 Args: 74 field: the original field. 75 index: the position of the original field in the struct. 76 ordinal: the ordinal of the field for serialization. 77 """ 78 self.field = field 79 self.index = index 80 self.ordinal = ordinal 81 self.size = self.GetSizeForKind(field.kind) 82 self.alignment = self.GetAlignmentForKind(field.kind) 83 self.offset = None 84 self.bit = None 85 self.min_version = None 86 87 88def GetPad(offset, alignment): 89 """Returns the pad necessary to reserve space so that |offset + pad| equals to 90 some multiple of |alignment|.""" 91 return (alignment - (offset % alignment)) % alignment 92 93 94def GetFieldOffset(field, last_field): 95 """Returns a 2-tuple of the field offset and bit (for BOOLs).""" 96 if (field.field.kind == mojom.BOOL and 97 last_field.field.kind == mojom.BOOL and 98 last_field.bit < 7): 99 return (last_field.offset, last_field.bit + 1) 100 101 offset = last_field.offset + last_field.size 102 pad = GetPad(offset, field.alignment) 103 return (offset + pad, 0) 104 105 106def GetPayloadSizeUpToField(field): 107 """Returns the payload size (not including struct header) if |field| is the 108 last field. 109 """ 110 if not field: 111 return 0 112 offset = field.offset + field.size 113 pad = GetPad(offset, 8) 114 return offset + pad 115 116 117class PackedStruct(object): 118 def __init__(self, struct): 119 self.struct = struct 120 # |packed_fields| contains all the fields, in increasing offset order. 121 self.packed_fields = [] 122 # |packed_fields_in_ordinal_order| refers to the same fields as 123 # |packed_fields|, but in ordinal order. 124 self.packed_fields_in_ordinal_order = [] 125 126 # No fields. 127 if (len(struct.fields) == 0): 128 return 129 130 # Start by sorting by ordinal. 131 src_fields = self.packed_fields_in_ordinal_order 132 ordinal = 0 133 for index, field in enumerate(struct.fields): 134 if field.ordinal is not None: 135 ordinal = field.ordinal 136 src_fields.append(PackedField(field, index, ordinal)) 137 ordinal += 1 138 src_fields.sort(key=lambda field: field.ordinal) 139 140 # Set |min_version| for each field. 141 next_min_version = 0 142 for packed_field in src_fields: 143 if packed_field.field.min_version is None: 144 assert next_min_version == 0 145 else: 146 assert packed_field.field.min_version >= next_min_version 147 next_min_version = packed_field.field.min_version 148 packed_field.min_version = next_min_version 149 150 if (packed_field.min_version != 0 and 151 mojom.IsReferenceKind(packed_field.field.kind) and 152 not packed_field.field.kind.is_nullable): 153 raise Exception("Non-nullable fields are only allowed in version 0 of " 154 "a struct. %s.%s is defined with [MinVersion=%d]." 155 % (self.struct.name, packed_field.field.name, 156 packed_field.min_version)) 157 158 src_field = src_fields[0] 159 src_field.offset = 0 160 src_field.bit = 0 161 dst_fields = self.packed_fields 162 dst_fields.append(src_field) 163 164 # Then find first slot that each field will fit. 165 for src_field in src_fields[1:]: 166 last_field = dst_fields[0] 167 for i in xrange(1, len(dst_fields)): 168 next_field = dst_fields[i] 169 offset, bit = GetFieldOffset(src_field, last_field) 170 if offset + src_field.size <= next_field.offset: 171 # Found hole. 172 src_field.offset = offset 173 src_field.bit = bit 174 dst_fields.insert(i, src_field) 175 break 176 last_field = next_field 177 if src_field.offset is None: 178 # Add to end 179 src_field.offset, src_field.bit = GetFieldOffset(src_field, last_field) 180 dst_fields.append(src_field) 181 182 183class ByteInfo(object): 184 def __init__(self): 185 self.is_padding = False 186 self.packed_fields = [] 187 188 189def GetByteLayout(packed_struct): 190 total_payload_size = GetPayloadSizeUpToField( 191 packed_struct.packed_fields[-1] if packed_struct.packed_fields else None) 192 bytes = [ByteInfo() for i in xrange(total_payload_size)] 193 194 limit_of_previous_field = 0 195 for packed_field in packed_struct.packed_fields: 196 for i in xrange(limit_of_previous_field, packed_field.offset): 197 bytes[i].is_padding = True 198 bytes[packed_field.offset].packed_fields.append(packed_field) 199 limit_of_previous_field = packed_field.offset + packed_field.size 200 201 for i in xrange(limit_of_previous_field, len(bytes)): 202 bytes[i].is_padding = True 203 204 for byte in bytes: 205 # A given byte cannot both be padding and have a fields packed into it. 206 assert not (byte.is_padding and byte.packed_fields) 207 208 return bytes 209 210 211class VersionInfo(object): 212 def __init__(self, version, num_fields, num_bytes): 213 self.version = version 214 self.num_fields = num_fields 215 self.num_bytes = num_bytes 216 217 218def GetVersionInfo(packed_struct): 219 """Get version information for a struct. 220 221 Args: 222 packed_struct: A PackedStruct instance. 223 224 Returns: 225 A non-empty list of VersionInfo instances, sorted by version in increasing 226 order. 227 Note: The version numbers may not be consecutive. 228 """ 229 versions = [] 230 last_version = 0 231 last_num_fields = 0 232 last_payload_size = 0 233 234 for packed_field in packed_struct.packed_fields_in_ordinal_order: 235 if packed_field.min_version != last_version: 236 versions.append( 237 VersionInfo(last_version, last_num_fields, 238 last_payload_size + HEADER_SIZE)) 239 last_version = packed_field.min_version 240 241 last_num_fields += 1 242 # The fields are iterated in ordinal order here. However, the size of a 243 # version is determined by the last field of that version in pack order, 244 # instead of ordinal order. Therefore, we need to calculate the max value. 245 last_payload_size = max(GetPayloadSizeUpToField(packed_field), 246 last_payload_size) 247 248 assert len(versions) == 0 or last_num_fields != versions[-1].num_fields 249 versions.append(VersionInfo(last_version, last_num_fields, 250 last_payload_size + HEADER_SIZE)) 251 return versions 252