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("Invalid kind: %s" % kind.spec) 60 return cls.kind_to_size[kind] 61 62 @classmethod 63 def GetAlignmentForKind(cls, kind): 64 if isinstance(kind, (mojom.Interface, mojom.AssociatedInterface)): 65 return 4 66 if isinstance(kind, mojom.Union): 67 return 8 68 return cls.GetSizeForKind(kind) 69 70 def __init__(self, field, index, ordinal): 71 """ 72 Args: 73 field: the original field. 74 index: the position of the original field in the struct. 75 ordinal: the ordinal of the field for serialization. 76 """ 77 self.field = field 78 self.index = index 79 self.ordinal = ordinal 80 self.size = self.GetSizeForKind(field.kind) 81 self.alignment = self.GetAlignmentForKind(field.kind) 82 self.offset = None 83 self.bit = None 84 self.min_version = None 85 86 87def GetPad(offset, alignment): 88 """Returns the pad necessary to reserve space so that |offset + pad| equals to 89 some multiple of |alignment|.""" 90 return (alignment - (offset % alignment)) % alignment 91 92 93def GetFieldOffset(field, last_field): 94 """Returns a 2-tuple of the field offset and bit (for BOOLs).""" 95 if (field.field.kind == mojom.BOOL and 96 last_field.field.kind == mojom.BOOL and 97 last_field.bit < 7): 98 return (last_field.offset, last_field.bit + 1) 99 100 offset = last_field.offset + last_field.size 101 pad = GetPad(offset, field.alignment) 102 return (offset + pad, 0) 103 104 105def GetPayloadSizeUpToField(field): 106 """Returns the payload size (not including struct header) if |field| is the 107 last field. 108 """ 109 if not field: 110 return 0 111 offset = field.offset + field.size 112 pad = GetPad(offset, 8) 113 return offset + pad 114 115 116class PackedStruct(object): 117 def __init__(self, struct): 118 self.struct = struct 119 # |packed_fields| contains all the fields, in increasing offset order. 120 self.packed_fields = [] 121 # |packed_fields_in_ordinal_order| refers to the same fields as 122 # |packed_fields|, but in ordinal order. 123 self.packed_fields_in_ordinal_order = [] 124 125 # No fields. 126 if (len(struct.fields) == 0): 127 return 128 129 # Start by sorting by ordinal. 130 src_fields = self.packed_fields_in_ordinal_order 131 ordinal = 0 132 for index, field in enumerate(struct.fields): 133 if field.ordinal is not None: 134 ordinal = field.ordinal 135 src_fields.append(PackedField(field, index, ordinal)) 136 ordinal += 1 137 src_fields.sort(key=lambda field: field.ordinal) 138 139 # Set |min_version| for each field. 140 next_min_version = 0 141 for packed_field in src_fields: 142 if packed_field.field.min_version is None: 143 assert next_min_version == 0 144 else: 145 assert packed_field.field.min_version >= next_min_version 146 next_min_version = packed_field.field.min_version 147 packed_field.min_version = next_min_version 148 149 if (packed_field.min_version != 0 and 150 mojom.IsReferenceKind(packed_field.field.kind) and 151 not packed_field.field.kind.is_nullable): 152 raise Exception("Non-nullable fields are only allowed in version 0 of " 153 "a struct. %s.%s is defined with [MinVersion=%d]." 154 % (self.struct.name, packed_field.field.name, 155 packed_field.min_version)) 156 157 src_field = src_fields[0] 158 src_field.offset = 0 159 src_field.bit = 0 160 dst_fields = self.packed_fields 161 dst_fields.append(src_field) 162 163 # Then find first slot that each field will fit. 164 for src_field in src_fields[1:]: 165 last_field = dst_fields[0] 166 for i in xrange(1, len(dst_fields)): 167 next_field = dst_fields[i] 168 offset, bit = GetFieldOffset(src_field, last_field) 169 if offset + src_field.size <= next_field.offset: 170 # Found hole. 171 src_field.offset = offset 172 src_field.bit = bit 173 dst_fields.insert(i, src_field) 174 break 175 last_field = next_field 176 if src_field.offset is None: 177 # Add to end 178 src_field.offset, src_field.bit = GetFieldOffset(src_field, last_field) 179 dst_fields.append(src_field) 180 181 182class ByteInfo(object): 183 def __init__(self): 184 self.is_padding = False 185 self.packed_fields = [] 186 187 188def GetByteLayout(packed_struct): 189 total_payload_size = GetPayloadSizeUpToField( 190 packed_struct.packed_fields[-1] if packed_struct.packed_fields else None) 191 bytes = [ByteInfo() for i in xrange(total_payload_size)] 192 193 limit_of_previous_field = 0 194 for packed_field in packed_struct.packed_fields: 195 for i in xrange(limit_of_previous_field, packed_field.offset): 196 bytes[i].is_padding = True 197 bytes[packed_field.offset].packed_fields.append(packed_field) 198 limit_of_previous_field = packed_field.offset + packed_field.size 199 200 for i in xrange(limit_of_previous_field, len(bytes)): 201 bytes[i].is_padding = True 202 203 for byte in bytes: 204 # A given byte cannot both be padding and have a fields packed into it. 205 assert not (byte.is_padding and byte.packed_fields) 206 207 return bytes 208 209 210class VersionInfo(object): 211 def __init__(self, version, num_fields, num_bytes): 212 self.version = version 213 self.num_fields = num_fields 214 self.num_bytes = num_bytes 215 216 217def GetVersionInfo(packed_struct): 218 """Get version information for a struct. 219 220 Args: 221 packed_struct: A PackedStruct instance. 222 223 Returns: 224 A non-empty list of VersionInfo instances, sorted by version in increasing 225 order. 226 Note: The version numbers may not be consecutive. 227 """ 228 versions = [] 229 last_version = 0 230 last_num_fields = 0 231 last_payload_size = 0 232 233 for packed_field in packed_struct.packed_fields_in_ordinal_order: 234 if packed_field.min_version != last_version: 235 versions.append( 236 VersionInfo(last_version, last_num_fields, 237 last_payload_size + HEADER_SIZE)) 238 last_version = packed_field.min_version 239 240 last_num_fields += 1 241 # The fields are iterated in ordinal order here. However, the size of a 242 # version is determined by the last field of that version in pack order, 243 # instead of ordinal order. Therefore, we need to calculate the max value. 244 last_payload_size = max(GetPayloadSizeUpToField(packed_field), 245 last_payload_size) 246 247 assert len(versions) == 0 or last_num_fields != versions[-1].num_fields 248 versions.append(VersionInfo(last_version, last_num_fields, 249 last_payload_size + HEADER_SIZE)) 250 return versions 251