Tagged Pointer
2020-04-11 本文已影响0人
mtry
写在前面
在阅读 runtime 源码 objc4-750.1 时，经常看到如果对象是isTaggedPointer的时候会有特殊处理。通过查阅资料发现这是一个能够提升对小对象读取速度和节省内存的技术。
本文主要是参考 objc4-750.1 ，考虑到时效性，不过大致原理不会变。
基本原理
对象在内存中是对齐的，它们的地址总是指针大小的整数倍，通常为16的倍数。对象指针是一个64位的整数，而为了对齐，一些位将永远是零。
Tagged Pointer 利用了这一现状，它使对象指针中非零位有了特殊的含义。在苹果的64位Objective-C实现中，若对象指针的最低有效位为1(即奇数)，则该指针为Tagged Pointer。这种指针不通过解引用isa来获取其所属类，而是通过接下来三位的一个类表的索引。该索引是用来查找所属类是采用 Tagged Pointer 的哪个类。剩下的60位则留给类来使用。
Tagged Pointer 有一个简单的应用，那就是NSNumber。它使用60位来存储数值。最低位置1。剩下3位为NSNumber的标志。在这个例子中，就可以存储任何所需内存小于60位的数值。
从外部看，Tagged Pointer 很像一个对象。它能够响应消息，因为 objc_msgSend 可以识别 Tagged Pointer。假设你调用 integerValue，它将从那60位中提取数值并返回。这样，每访问一个对象，就省下了一次真正对象的内存分配，省下了一次间接取值的时间。同时引用计数可以是空指令，因为没有内存需要释放。对于常用的类，这将是一个巨大的性能提升。
底层实现
// 通过对象指针判断是否为 Tagged Pointer 指针
// 判断判断条件是，指针地址的值转换为二进制，判断最低位是否为 1（也就是奇数）。
define _OBJC_TAG_MASK 1UL
static inline bool _objc_isTaggedPointer(const void * _Nullable ptr)
{
return ((uintptr_t)ptr & _OBJC_TAG_MASK) == _OBJC_TAG_MASK;
}
苹果为了让 Tagged Pointer 指针，看起来不那么特别，也有可能出于其他原因，总之对 Tagged Pointer 指针进行了加解密处理。
extern uintptr_t objc_debug_taggedpointer_obfuscator;
// 加密
static inline void * _Nonnull _objc_encodeTaggedPointer(uintptr_t ptr)
{
return (void *)(objc_debug_taggedpointer_obfuscator ^ ptr);
}
// 解码
static inline uintptr_t _objc_decodeTaggedPointer(const void * _Nullable ptr)
{
return (uintptr_t)ptr ^ objc_debug_taggedpointer_obfuscator;
}
// objc_debug_taggedpointer_obfuscator 在运行时初始化的时候，随机生成。
static void initializeTaggedPointerObfuscator(void)
{
if (sdkIsOlderThan(10_14, 12_0, 12_0, 5_0, 3_0) || DisableTaggedPointerObfuscation ) {
objc_debug_taggedpointer_obfuscator = 0;
} else {
arc4random_buf(&objc_debug_taggedpointer_obfuscator, sizeof(objc_debug_taggedpointer_obfuscator));
// 使 _OBJC_TAG_MASK（最低位）位置，永远为 0
// 目的是，原始指针可以在不解码的情况下，判断是否为 Tagged Pointer 指针
objc_debug_taggedpointer_obfuscator &= ~_OBJC_TAG_MASK;
}
}
接下来，看一下从 Tagged Pointer 指针取值操作
// 支持 Tagged Pointer 指针的类索引
enum objc_tag_index_t : uint16_t
{
/*普通类 第2~4位：类标记索 */
OBJC_TAG_NSAtom = 0, //000
OBJC_TAG_1 = 1, //001
OBJC_TAG_NSString = 2, //010
OBJC_TAG_NSNumber = 3, //011
OBJC_TAG_NSIndexPath = 4, //100
OBJC_TAG_NSManagedObjectID = 5, //101 CoreData 中使用
OBJC_TAG_NSDate = 6, //110
OBJC_TAG_RESERVED_7 = 7, //111
//如果第2~4位标记为 OBJC_TAG_RESERVED_7，那么就用第5~12位，扩展类索引
/*扩展类 第5~12位：扩展类标记索引，目前暂时只有 8 种*/
OBJC_TAG_Photos_1 = 8,
OBJC_TAG_Photos_2 = 9,
OBJC_TAG_Photos_3 = 10,
OBJC_TAG_Photos_4 = 11,
OBJC_TAG_XPC_1 = 12,
OBJC_TAG_XPC_2 = 13,
OBJC_TAG_XPC_3 = 14,
OBJC_TAG_XPC_4 = 15,
//用于协助第2~4位、第5~12位处理
OBJC_TAG_First60BitPayload = 0,
OBJC_TAG_Last60BitPayload = 6,
OBJC_TAG_First52BitPayload = 8,
OBJC_TAG_Last52BitPayload = 263,
OBJC_TAG_RESERVED_264 = 264
};
#define _OBJC_TAG_MASK 1UL
#define _OBJC_TAG_INDEX_SHIFT 1
#define _OBJC_TAG_SLOT_SHIFT 0
#define _OBJC_TAG_PAYLOAD_LSHIFT 0
#define _OBJC_TAG_PAYLOAD_RSHIFT 4
#define _OBJC_TAG_EXT_MASK 0xfUL
#define _OBJC_TAG_EXT_INDEX_SHIFT 4
#define _OBJC_TAG_EXT_SLOT_SHIFT 4
#define _OBJC_TAG_EXT_PAYLOAD_LSHIFT 0
#define _OBJC_TAG_EXT_PAYLOAD_RSHIFT 12
#define _OBJC_TAG_INDEX_MASK 0x7
#define _OBJC_TAG_EXT_INDEX_MASK 0xff
// 通过 Tagged Pointer 指针，获取当前指针对应的类的索引值
static inline objc_tag_index_t _objc_getTaggedPointerTag(const void * _Nullable ptr)
{
// 解码指针
uintptr_t value = _objc_decodeTaggedPointer(ptr);
// 获取第2~4位的值 (value >> 1) & 0x7
uintptr_t basicTag = (value >> _OBJC_TAG_INDEX_SHIFT) & _OBJC_TAG_INDEX_MASK;
// 获取第5~12位的值 (value >> 4) & 0xff
uintptr_t extTag = (value >> _OBJC_TAG_EXT_INDEX_SHIFT) & _OBJC_TAG_EXT_INDEX_MASK;
if (basicTag == _OBJC_TAG_INDEX_MASK) {
return (objc_tag_index_t)(extTag + OBJC_TAG_First52BitPayload);
} else {
return (objc_tag_index_t)basicTag;
}
}
// 通过 Tagged Pointer 指针，获取存储对象的值
static inline uintptr_t _objc_getTaggedPointerValue(const void * _Nullable ptr)
{
uintptr_t value = _objc_decodeTaggedPointer(ptr);
// 获取第2~4位的值 (value >> 1) & 0x7
uintptr_t basicTag = (value >> _OBJC_TAG_INDEX_SHIFT) & _OBJC_TAG_INDEX_MASK;
if (basicTag == _OBJC_TAG_INDEX_MASK) {
// (value << 0) >> 12
return (value << _OBJC_TAG_EXT_PAYLOAD_LSHIFT) >> _OBJC_TAG_EXT_PAYLOAD_RSHIFT;
} else {
// (value << 0) >> 4
return (value << _OBJC_TAG_PAYLOAD_LSHIFT) >> _OBJC_TAG_PAYLOAD_RSHIFT;
}
}
// 把一个整形值，转换为 Tagged Pointer 指针
static inline void * _Nonnull _objc_makeTaggedPointer(objc_tag_index_t tag, uintptr_t value)
{
if (tag <= OBJC_TAG_Last60BitPayload)
{// 普通类
// 1 | (tag << 1) | value << 4
uintptr_t result =
(_OBJC_TAG_MASK |
((uintptr_t)tag << _OBJC_TAG_INDEX_SHIFT) |
((value << _OBJC_TAG_PAYLOAD_RSHIFT) >> _OBJC_TAG_PAYLOAD_LSHIFT));
return _objc_encodeTaggedPointer(result);
}
else
{// 扩展类
// 0xf | (tag - 8) << 4 | (value << 12)
uintptr_t result =
(_OBJC_TAG_EXT_MASK |
((uintptr_t)(tag - OBJC_TAG_First52BitPayload) << _OBJC_TAG_EXT_INDEX_SHIFT) |
((value << _OBJC_TAG_EXT_PAYLOAD_RSHIFT) >> _OBJC_TAG_EXT_PAYLOAD_LSHIFT));
return _objc_encodeTaggedPointer(result);
}
}
接下来，最后看一段根据 objc_tag_index_t 获取对应的类
// 把 cls 根据 objc_tag_index_t 注册
void _objc_registerTaggedPointerClass(objc_tag_index_t tag, Class cls)
{
if (objc_debug_taggedpointer_mask == 0) {
_objc_fatal("tagged pointers are disabled");
}
Class *slot = classSlotForTagIndex(tag);
if (!slot) {
_objc_fatal("tag index %u is invalid", (unsigned int)tag);
}
Class oldCls = *slot;
if (cls && oldCls && cls != oldCls) {
_objc_fatal("tag index %u used for two different classes "
"(was %p %s, now %p %s)", tag,
oldCls, oldCls->nameForLogging(),
cls, cls->nameForLogging());
}
*slot = cls;
// Store a placeholder class in the basic tag slot that is
// reserved for the extended tag space, if it isn't set already.
// Do this lazily when the first extended tag is registered so
// that old debuggers characterize bogus pointers correctly more often.
if (tag < OBJC_TAG_First60BitPayload || tag > OBJC_TAG_Last60BitPayload) {
Class *extSlot = classSlotForBasicTagIndex(OBJC_TAG_RESERVED_7);
if (*extSlot == nil) {
extern objc_class OBJC_CLASS_$___NSUnrecognizedTaggedPointer;
*extSlot = (Class)&OBJC_CLASS_$___NSUnrecognizedTaggedPointer;
}
}
}
// 通过 objc_tag_index_t 获取，对应的类
Class _objc_getClassForTag(objc_tag_index_t tag)
{
Class *slot = classSlotForTagIndex(tag);
if (slot) return *slot;
else return nil;
}
#define _OBJC_TAG_SLOT_COUNT 16
#define _OBJC_TAG_EXT_SLOT_COUNT 256
extern "C" {
// 个人觉得这里没必要 *2
extern Class objc_debug_taggedpointer_classes[_OBJC_TAG_SLOT_COUNT*2];
extern Class objc_debug_taggedpointer_ext_classes[_OBJC_TAG_EXT_SLOT_COUNT];
}
#define objc_tag_classes objc_debug_taggedpointer_classes
#define objc_tag_ext_classes objc_debug_taggedpointer_ext_classes
// 根据 objc_tag_index_t 获取普通类
static Class *classSlotForBasicTagIndex(objc_tag_index_t tag)
{
uintptr_t tagObfuscator = ((objc_debug_taggedpointer_obfuscator
>> _OBJC_TAG_INDEX_SHIFT)
& _OBJC_TAG_INDEX_MASK);
uintptr_t obfuscatedTag = tag ^ tagObfuscator;
// Array index in objc_tag_classes includes the tagged bit itself
// 恢复原指针地址（16进制）最低的1位的值，当做索引
return &objc_tag_classes[(obfuscatedTag << 1) | 1];
}
// 根据 objc_tag_index_t，获取类（普通类或扩展类）
static Class *classSlotForTagIndex(objc_tag_index_t tag)
{
if (tag >= OBJC_TAG_First60BitPayload && tag <= OBJC_TAG_Last60BitPayload) {
return classSlotForBasicTagIndex(tag);
}
if (tag >= OBJC_TAG_First52BitPayload && tag <= OBJC_TAG_Last52BitPayload) {
int index = tag - OBJC_TAG_First52BitPayload;
uintptr_t tagObfuscator = ((objc_debug_taggedpointer_obfuscator
>> _OBJC_TAG_EXT_INDEX_SHIFT)
& _OBJC_TAG_EXT_INDEX_MASK);
// 恢复原指针地址（16进制）第2～3位的值，当做索引
return &objc_tag_ext_classes[index ^ tagObfuscator];
}
return nil;
}
小结
- 指针最低位用于判断是否为 Tagged Pointer 指针；
- 接下来第2～4位，用于存储所属类索引值；
- 当第2～4位为 111 时，这时需要增加扩展类，用第 5～12 位存储扩展类的索引值。
巧妙应用
通过上面的内容，可以确定基本原理，也可以确定不是所有的 NSString、NSNumber 都是通过 Tagged Pointer 指针存储的，只有满足一定条件才能触发。
由于值的存储部分没有源码，只能通过一些猜测和验证。
{
OBJC_TAG_NSAtom = 0,
OBJC_TAG_1 = 1,
OBJC_TAG_NSString = 2,
OBJC_TAG_NSNumber = 3,
OBJC_TAG_NSIndexPath = 4,
OBJC_TAG_NSManagedObjectID = 5, // CoreDate 中使用
OBJC_TAG_NSDate = 6,
}
下面分析的类型 NSNumber 和 NSString
关于 NSNumber
根据底层实现，可以写一个把对象地址解码还原为二进制地址，方便观察。
extern uintptr_t objc_debug_taggedpointer_obfuscator;
NSString *toBinary(id obj)
{
void *ptr;
ptr = (void *)CFBridgingRetain(obj);
// 指针解码
uintptr_t p = (uintptr_t)ptr ^ objc_debug_taggedpointer_obfuscator;
NSMutableString *binarys = [NSMutableString string];
while (p) {
[binarys insertString: (p & 1 ? @"1" : @"0") atIndex:0];
p = p >> 1;
}
return binarys;
}
int main(int argc, const char * argv[]) {
NSNumber *numberInt = [NSNumber numberWithInt:100];
NSNumber *numberLong = [NSNumber numberWithLong:100];
NSNumber *numberFloat = [NSNumber numberWithFloat:100];
NSNumber *numberDouble = [NSNumber numberWithDouble:100];
NSLog(@"numberInt:%@", toBinary(numberInt));
NSLog(@"numberLong:%@", toBinary(numberLong));
NSLog(@"numberFloat:%@", toBinary(numberFloat));
NSLog(@"numberDouble:%@", toBinary(numberDouble));
return 0;
}
/*
打印为：
numberInt:110010000100111
numberLong:110010000110111
numberFloat:110010001000111
numberDouble:110010001010111
*/
- 第 1 位：都为 1，表示都是 Tagged Pointer 指针
- 第 2～4 位：分别是 011，对应 OBJC_TAG_NSNumber
- 第 5～8 位：数字类型标记
| 第 5～8 位 | 对应类型 |
|---|---|
| 0010 | int |
| 0011 | long |
| 0100 | float |
| 0101 | double |
| ... | ... |
再来实验一下 NSNumber 最大可以取多少位
BOOL isTaggedPointerObj(id obj)
{
void *ptr = (void *)CFBridgingRetain(obj);
return (uintptr_t)ptr & 1;
}
int main(int argc, const char * argv[]) {
NSNumber *number;
NSInteger b = 1;
do {
number = [NSNumber numberWithUnsignedLongLong:1ull << b];
NSLog(@"%02ld %@", b, toBinary(number));
b++;
} while (isTaggedPointerObj(number));
return 0;
}
/*
打印结果
01 100110111
02 1000110111
03 10000110111
04 100000110111
05 1000000110111
06 10000000110111
07 100000000110111
08 1000000000110111
09 10000000000110111
10 100000000000110111
11 1000000000000110111
12 10000000000000110111
13 100000000000000110111
14 1000000000000000110111
15 10000000000000000110111
16 100000000000000000110111
17 1000000000000000000110111
18 10000000000000000000110111
19 100000000000000000000110111
20 1000000000000000000000110111
21 10000000000000000000000110111
22 100000000000000000000000110111
23 1000000000000000000000000110111
24 10000000000000000000000000110111
25 100000000000000000000000000110111
26 1000000000000000000000000000110111
27 10000000000000000000000000000110111
28 100000000000000000000000000000110111
29 1000000000000000000000000000000110111
30 10000000000000000000000000000000110111
31 100000000000000000000000000000000110111
32 1000000000000000000000000000000000110111
33 10000000000000000000000000000000000110111
34 100000000000000000000000000000000000110111
35 1000000000000000000000000000000000000110111
36 10000000000000000000000000000000000000110111
37 100000000000000000000000000000000000000110111
38 1000000000000000000000000000000000000000110111
39 10000000000000000000000000000000000000000110111
40 100000000000000000000000000000000000000000110111
41 1000000000000000000000000000000000000000000110111
42 10000000000000000000000000000000000000000000110111
43 100000000000000000000000000000000000000000000110111
44 1000000000000000000000000000000000000000000000110111
45 10000000000000000000000000000000000000000000000110111
46 100000000000000000000000000000000000000000000000110111
47 1000000000000000000000000000000000000000000000000110111
48 10000000000000000000000000000000000000000000000000110111
49 100000000000000000000000000000000000000000000000000110111
50 1000000000000000000000000000000000000000000000000000110111
51 10000000000000000000000000000000000000000000000000000110111
52 100000000000000000000000000000000000000000000000000000110111
53 1000000000000000000000000000000000000000000000000000000110111
54 10000000000000000000000000000000000000000000000000000000110111
55 100000000000000000000000000000000000000000000000000000000110111
56 1010101101111110011011010110111010110110011000001101000011111010
*/
也就是说：小于等于 2^55 的整形都是通过 Tagged Pointer 指针存储的。当然对于 double 存储方式应该有所不同，就不再验证了，总之普通业务开发一般都是够用的。
观察 NSIndexPath、NSDate 类的定义
@interface NSIndexPath : NSObject <NSCopying, NSSecureCoding> {
@private
NSUInteger *_indexes;
NSUInteger _length;
void *_reserved;
}
+ (instancetype)indexPathWithIndex:(NSUInteger)index;
+ (instancetype)indexPathWithIndexes:(const NSUInteger [_Nullable])indexes length:(NSUInteger)length;
- (instancetype)initWithIndexes:(const NSUInteger [_Nullable])indexes length:(NSUInteger)length NS_DESIGNATED_INITIALIZER;
- (instancetype)initWithIndex:(NSUInteger)index;
@property (readonly) NSUInteger length;
@end
typedef double NSTimeInterval;
#define NSTimeIntervalSince1970 978307200.0
@interface NSDate : NSObject <NSCopying, NSSecureCoding>
@property (readonly) NSTimeInterval timeIntervalSinceReferenceDate;
- (instancetype)init NS_DESIGNATED_INITIALIZER;
- (instancetype)initWithTimeIntervalSinceReferenceDate:(NSTimeInterval)ti NS_DESIGNATED_INITIALIZER;
@end
可以发现，NSIndexPath 的 length 属性是 NSUInteger 和 NSDate 的 timeIntervalSinceReferenceDate 属性是 double 类型，完全可以通过类型 NSNumber 的方式进行存储。
猜测：当一个类的对象表现可以通过一个数字转换而来，就可以考虑通过 Tagged Pointer 指针存储，当然这个数字是有范围的，不过这个数字的范围还是很大的。
关于 NSSting
字符串的编码方式，【译】采用Tagged Pointer的字符串 分析的很好了，我就总结一下。
int main(int argc, const char * argv[]) {
NSString *str1 = [@"1".mutableCopy copy]; // [NSString stringWithFormat:@"1"]; 这样方式也可以
NSString *str2 = [@"11".mutableCopy copy];
NSString *str3 = [@"111".mutableCopy copy];
NSString *str4 = [@"1111".mutableCopy copy];
NSLog(@"%@", toBinary(str1));
NSLog(@"%@", toBinary(str2));
NSLog(@"%@", toBinary(str3));
NSLog(@"%@", toBinary(str4));
//000000000000000000000000110001 0001 010 1
//000000000000000011000100110001 0010 010 1
//000000001100010011000100110001 0011 010 1
//110001001100010011000100110001 0100 010 1
return 0;
}
mutableCopy/copy 是必要的。原因有两个。首先，尽管像 @"a" 这样的字符串可以存储为一个 Tagged Pointer，但是字符串常量却从不存储为 Tagged Pointer。字符串常量必须在不同的操作系统版本下保持二进制兼容，而 Tagged Pointer的内部细节是没有保证的。其能使用的前提是Tagged Pointer 在运行时总是由 Apple 的代码生成，如果编译器把它们嵌入二进制里，那么前提就被打破了（字符串常量就是这样）。因此我们需要 copy 常量字符串来获取 Tagged Pointer。</br></br>
mutableCopy 也是必要的，因为 NSString 太聪明，而且也知道一个不可变字符串的副本是一个毫无意义的操作，所以它会返回原字符串的当作 “copy”。字符串常量是不可变的，所以 [@"a" copy] 结果只是 @"a"。一个可变量的副本强迫它产生真正副本，这样一个可变量副本的不可变的副本足以让系统给我们产生一个采用 Tagged Pointer 的字符串。</br></br>
注意不要在你自己的代码里依赖这些细节！这是 NSString 的当前情况，它随时可能改变。
- 第 1 位：为 1，表示都是 Tagged Pointer 指针
- 第 2～4 位：为 010，对应 OBJC_TAG_NSString
- 第 5～8 位：字符串的长度
剩下的 56 位就可以存储字符串，这里会遇到一个问题，用多少位存储一个字符问题。比如，如果用 ASCII 编码，一个有 127 个字符，需要至少需要 7 位存储一个字符（2^7 = 128），实际上苹果用 ASCII 编码的时候，用了 8 位来存储，因此长度最长为 7；为了尽可能的增加字符串长度，苹果筛选出常用字符，进行重新编码。
采用 Tagged Pointer 的字符串的结构:
- 字符串长度介于0到7，直接用八位编码存储字符串，ASCII编码
- 字符串长度是8或9，用六位编码存储字符串，编码表
eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX - 字符串长度是10或11，用五位编码存储字符串，编码表
eilotrm.apdnsIc ufkMShjTRxgC4013
验证一下
int main(int argc, const char * argv[]) {
NSString *q = @"q"; //八位编码
NSString *w = @"w"; //六位编码
NSString *a = @"a"; //五位编码
NSMutableString *strq = [NSMutableString string];
NSMutableString *strw = [NSMutableString string];
NSMutableString *stra = [NSMutableString string];
for (NSInteger i = 1; i <= 12; i++)
{
[strq appendString:q];
[strw appendString:w];
[stra appendString:a];
NSLog(@"%02ld: %@ %@ %@", i, toBinary([strq.mutableCopy copy]), toBinary([strw.mutableCopy copy]), toBinary([stra.mutableCopy copy]));
}
return 0;
}
/*
打印如下
01: 0000000000000000000000000000000000000000000000000111000100010101 0000000000000000000000000000000000000000000000000111011100010101 0000000000000000000000000000000000000000000000000110000100010101
02: 0000000000000000000000000000000000000000011100010111000100100101 0000000000000000000000000000000000000000011101110111011100100101 0000000000000000000000000000000000000000011000010110000100100101
03: 0000000000000000000000000000000001110001011100010111000100110101 0000000000000000000000000000000001110111011101110111011100110101 0000000000000000000000000000000001100001011000010110000100110101
04: 0000000000000000000000000111000101110001011100010111000101000101 0000000000000000000000000111011101110111011101110111011101000101 0000000000000000000000000110000101100001011000010110000101000101
05: 0000000000000000011100010111000101110001011100010111000101010101 0000000000000000011101110111011101110111011101110111011101010101 0000000000000000011000010110000101100001011000010110000101010101
06: 0000000001110001011100010111000101110001011100010111000101100101 0000000001110111011101110111011101110111011101110111011101100101 0000000001100001011000010110000101100001011000010110000101100101
07: 0111000101110001011100010111000101110001011100010111000101110101 0111011101110111011101110111011101110111011101110111011101110101 0110000101100001011000010110000101100001011000010110000101110101
08: 0001011001101001100101101001011000111000010110101000100101100010 0000000010010010010010010010010010010010010010010010010010000101 0000000000100000100000100000100000100000100000100000100010000101
09: 0001011001101001100101101001011000111000010111010111001100000010 0010010010010010010010010010010010010010010010010010010010010101 0000100000100000100000100000100000100000100000100000100010010101
10: 0001011001101001100101101001011000111000010111010111001010010010 0001011001101001100101101001011000111000010111010110100001000010 0000000100001000010000100001000010000100001000010000100010100101
11: 0001011001101001100101101001011000111000010111010110111000100010 0001011001101001100101101001011000111000010111010111010011100010 0010000100001000010000100001000010000100001000010000100010110101
12: 0001011001101001100101101001011000111000010111010111010111010010 0001011001101001100101101001011000111000010111010111011011000010 0001011001101001100101101001011000111000010111010110101111110010
*/
