Сейчас мы наблюдаем развитие очень важного для текущей эпохи противоречия. Оно заключается в том что существование интернета противоречит существованию государств. Любых государств.

Дело в том, что государство — это юрисдикция на определенной территории. Когда ты пересекаешь границу, ты начинаешься подчиняться законам, принятым в этих границах. Государство контролирует свою территорию и не пускает на нее другие государства.

А в интернете никакой территории нет. Ну то есть физически конечно все компьютеры где-то расположены, но в виртуальном пространстве это не заметно. Все находятся везде, все имеют доступ ко всему.

И это впрямую противоречит тому как устроено государство. Потому что появляется возможность нарушителю законов одного государства делать это удаленно, находясь на территории другого. Он может оттуда рассылать спам, вымогать деньги, взламывать системы, рассылать информацию, которую другое государство желает цензурировать.

И в итоге государства начинают активно бороться с интернетом. Не только в России, разумеется. Я помню, когда API фейсбука приводили в пример Вконтакту как более открытое. А потом в США начался политический кризис, связанный с выборами Трампа, и Фейсбук зарегулировали таким образом, что для использования его API нужно пройти неимеверное количество бюрократии. Я когда несколько лет назад пробовать делать приложения, интегрированные с фейсбуком, в итоге просто отказался от этого. Надо совершать кучу бесссмысленных действий, и никаких гарантий, что тебе дадут этот доступ.

Но проблема в том, что интернет уже существует. Он уже связывает человечество воедино. Люди уже посмотрели друг на друга на ютубе, и видят, что люди везде примерно одинаковые. И тем меньше понимают, если все настолько одинаковые, то зачем их настолько разделять.

Нет, безусловно, есть культурные различия. Но чем больше люди обмениваются информацией друг с другом, тем больше их культуры выравниваются. Они друг друга взаимообогащают и становятся все больше похожи друг на друга.

Глобализация — это уровень информационных и транспортных технологий. За последние 50 лет эти технологии развились чрезвычайно и продолжают развиваться. Объективная реальность приводит ко все большему объединению человечества. Но накопившиеся на протяжении истории противоречия все еще существуют и приводят к попыткам остановить это объединение.

Мне кажется объединение победит. Не знаю когда и с какой скоростью. Но аргументация «почему они не мы, а мы не они» звучит все менее и менее убедительно. Потому что становится все проще сравнить «их» и «нас» — и не увидеть разницы.

Из всего вышесказанного, кстати, не следует что если интернет победит государства, то воцарится анархия. Просто если общество становится глобальным, то и система управления станет глобальной.

У меня есть афоризм насчет конспирологии про мировое правительства. Он состоит из двух пунктов:

1. Мирового правительства не существует.
2. Это очень плохо, что его не существует, его надо создать!

На самом деле это не афоризм, на мой взгляд, если планета становится единым обществом, то и система управления этим обществом будет единой. Я кстати при этом вовсе не говорю про США. Возможно, у США и был шанс создать мировое правительство, но тогда им следовало включить в НАТО Россию и Китай еще в 90-х и распределить между ними власть над миром.

На самом деле, мировое правительство по определению не может быть властью одного государства. Оно если и будет, то будет обладать совсем другой формой. Может оно возникнет на базе БРИКС. Может ООН. Может к тому времени когда оно появится, будут вообще другие международные структуры. Это пока невозможно предсказать.

В любом случае в ближайшие годы будет продолжаться как процесс объективной глобализации, так и процесс борьбы с ней. Государства будут с одной стороны пытаться сохранить свои юрисдикции, с другой стороны искать пути интеграции друг с другом, раз это позволяют технологии. Будут дальнейшие попытки создания надгосударственных структур. Будет продолжения взаимного влияния разных культур друг на друга.

Безусловно, это не означает, что весь мир станет монокультурным и везде будут одинаковые правила. Без разнообразия цивилизация утратит способность к выживанию. Но эти культуры и эти правила будут распределены не так как сейчас. Не знаю точно, как, но возможность жить по-разному все-таки сохранится.

P. S. Кстати, одно из следствий развитие ИИ заключается в том, что он скорее всего окончательно убьет анонимность в интернете.

Потому что люди и так страдают от спам-ботов и скам-ботов. А благодаря ИИ они становятся настолько умными, что становится критически важно знать, что тебе пишет реальный, живой, подтвержденный человек.

И в итоге все больше народу будут только за тотальную идентификацию людей в интернете. Потому что спам и мошенники всех достали. Анонимность все больше будет уходить в «даркнет», где никто не гарантирует твою безопасность.

Впрочем, полагаю, никнеймы иметь не запретят. Они прикольные. Но при этом рядом с никнеймами будет висеть галка «да, это живой человек из такой-то страны».

Надеюсь анонимные имиджборды тоже уцелеют. Просто от них потребуют вешать предупреждения «здесь все анонимусы, никому не верь».

Главное, не уничтожить культуру анонимности целиком. Она очень интересна и позволяет создавать удивительные коллективные произведения. Надо только понять, как ее совместить с безопасностью. Интересно, какие появятся решения в этой области.

Современные стандарты разработки пользовательских приложений выдвигают определенные требования к шифрованию информации. Например, документ RFC-7539 содержит подробную и исчерпывающую информацию о том, какие алгоритмы рекомендуется применять и как программировать некоторые из них. Далее предлагается к подробному рассмотрению один из этих алгоритмов — ChaCha20.

Разработка

Сначала нужно определить типы входных и выходных данных. Так как речь идет о шифровании данных, то вся работа заключается в манипулировании битами. Не имеет значение, что нужно шифровать, будь то текст, изображение или видео. Каждый из этих типов возможно преобразовать в набор битов и байтов, после чего применять конкретный алгоритм. Таким образом, основными типами, с которыми работает библиотека это байт — UInt8 (Byte) и последовательность из четырех байтов — UInt32 (Word).

typealias Byte = UInt8

final class Word {          // MARK: - Types          typealias Value = UInt32          // MARK: - Properties          var value: Value          // MARK: - Lifecycle          init(_ value: Value) {         self.value = value     }          init(bytes: [Byte]) throws {         value = 0         value = try getValue(from: bytes)     }          // MARK: - Methods          func getBytes() -> [Byte] {         var bytes: [Byte] = []                  for shift in stride(from: 24, through: 0, by: -8) {             let byte = Byte(truncatingIfNeeded: value.bigEndian >> shift)             bytes.append(byte)         }                  return bytes     }          private func getValue(from bytes: [Byte]) throws -> Value {         guard bytes.count == 4 else {             throw CryptoError.invalidSize         }          var value: Value = 0         let chunk = bytes[0..<bytes.count]          for (index, byte) in chunk.reversed().enumerated() {             var partition = Value(byte)             partition <<= byte.bitWidth * index             value |= partition.bigEndian         }          return value     } }

Определив типы данных, нужно инициализировать начальное состояние, используя ключ подписи и так называемый nonce. Здесь все предельно понятно, типы данных преобразуются к массиву байт и задают начальное состояние объекта.

final class ChaCha20 {          // MARK: - Properties          private var state: [Word]          // MARK: - Lifecycle          init(_ key: [Byte], _ nonce: [Byte]) throws {         state = [Word](repeating: Word(0), count: 16)                  state[0] = Word(0x61707865)         state[1] = Word(0x3320646e)         state[2] = Word(0x79622d32)         state[3] = Word(0x6b206574)                  let keyWordsIndexes = 4...11         let nonceWordsIndexes = 13...15                  for index in keyWordsIndexes {             let offset = (index - keyWordsIndexes.lowerBound) * 4             let bytes = key[offset..<offset + 4]             state[index] = try Word(bytes: Array(bytes))         }                  for index in nonceWordsIndexes {             let offset = (index - nonceWordsIndexes.lowerBound) * 4             let bytes = nonce[offset..<offset + 4]             state[index] = try Word(bytes: Array(bytes))         }     } }

RFC-7539 секция 2.3. Рекомендации на тему того, какие значения нужно указывать в качестве констант, однако у разработчика есть возможность задать собственные величины. Например, первые четыре значения state, а также значение счетчика операций state[12] (будет показано ниже) и количество итераций выполнения цикла формирования битовой маски (тоже будет показано ниже).

RFC-7539 секция 2.1. Главным методом для осуществления криптографического шифрования является quarterRound(_:_:_:_:). С его помощью над четырьмя числами проводится операции по изменению значений их битов.

Забегая наперед, нужно сказать, что ключевой операцией здесь является исключающее или (XOR). Именно по этой причине алгоритм достаточно выполнить один раз для шифрования и еще один раз для дешифрования.

private func quarterRound(_ a: Word, _ b: Word, _ c: Word, _ d: Word) {     a.value &+= b.value     d.value ^= a.value     d.value <<<= 16          c.value &+= d.value     b.value ^= c.value     b.value <<<= 12      a.value &+= b.value     d.value ^= a.value     d.value <<<= 8      c.value &+= d.value     b.value ^= c.value     b.value <<<= 7 }

Обратите внимание на наличие специального оператора <<<=, который выполняет круговое смещение битов. То есть старшие биты становятся младшими вместо обнуления младших. Так исключается потеря данных во время операций.

import Foundation  // MARK: - BinaryIntegerExtensions  infix operator <<< : BitwiseShiftPrecedence extension BinaryInteger where Self: UnsignedInteger {     static func <<<(target: Self, shiftAmount: Int) -> Self {         guard shiftAmount >= 0 else {             return target >>> -shiftAmount         }                  return (target << shiftAmount) | (target >> (target.bitWidth - shiftAmount))     } }  infix operator <<<= : BitwiseShiftPrecedence extension BinaryInteger where Self: UnsignedInteger {     static func <<<=(target: inout Self, shiftAmount: Int) {         target = target <<< shiftAmount     } }  infix operator >>> : BitwiseShiftPrecedence extension BinaryInteger where Self: UnsignedInteger {     static func >>>(target: Self, shiftAmount: Int) -> Self {         guard shiftAmount >= 0 else {             return target <<< -shiftAmount         }                  return (target >> shiftAmount) | (target << (target.bitWidth - shiftAmount))     } }  infix operator >>>= : BitwiseShiftPrecedence extension BinaryInteger where Self: UnsignedInteger {     static func >>>=(target: inout Self, shiftAmount: Int) {         target = target >>> shiftAmount     } }

RFC-7539 секция 2.3. Метод по формированию и наложению битовой маски blockFunction(counter:). Здесь используется state, определенный пользователем ключом и nonce во время инициализации.

private func blockFunction(counter: Int) -> [Word] {     let counterIndex = 12     state[counterIndex] = Word(UInt32(counter))          var workingState: [Word] = []          for word in state {         let value = word.value         let workingWord = Word(value)         workingState.append(workingWord)     }          for _ in 0..<10 {         quarterRound(workingState[0], workingState[4], workingState[8], workingState[12])         quarterRound(workingState[1], workingState[5], workingState[9], workingState[13])         quarterRound(workingState[2], workingState[6], workingState[10], workingState[14])         quarterRound(workingState[3], workingState[7], workingState[11], workingState[15])                  quarterRound(workingState[0], workingState[5], workingState[10], workingState[15])         quarterRound(workingState[1], workingState[6], workingState[11], workingState[12])         quarterRound(workingState[2], workingState[7], workingState[8], workingState[13])         quarterRound(workingState[3], workingState[4], workingState[9], workingState[14])     }          for index in 0..<state.count {         let state = state[index]         let workingState = workingState[index]         workingState.value &+= state.value     }          return workingState }

Как говорилось выше, количество итераций выполнения цикла определяется разработчиком и может иметь любые значения. Кстати, алгоритм называется ChaCha20 как раз-таки потому, что здесь происходит круговое смещение битов 10 раз для каждой из колон workingState и 10 раз для диагоналей workingState.

RFC-7539 секция 2.4. Криптование данных реализовано блоками по 64 байта. Входные данные разбиваются на блоки, для каждого из которых формируется своя битовая маска, которая после накладывается на блок.

func encrypt(_ message: [Byte]) -> [Byte] {     var result: [Byte] = []          let blockSize = 64     var mask: [Byte] = []     var j = 0     var counter = 0          for i in 0..<message.count {         if i % blockSize == 0 {             j = 0             counter += 1                          let workingState = blockFunction(counter: counter)             mask = workingState.reduce(into: []) { partialResult, word in                 let maskBytes = word.getBytes()                 partialResult.append(contentsOf: maskBytes)             }         }                  let encryptedByte = message[i] ^ mask[j]         result.append(encryptedByte)                  j += 1     }          return result }

И здесь тоже, обратите внимание на то, что значение счетчика операций определяется разработчиком и может иметь любые значения. В данной статье все константы были указаны в соответсвии с требованиями документа RFC-7539. Манипуляции по модификации константных значений носят лишь рекомендательный характер.

Заключение

Ядром алгоритма шифрования является в применение операции исключающее или. И это достаточно разумно, поскольку отсутствует необходимость в разработке метода дешифрования. Также, преимуществом является возможность определения собственных значений некоторых констант, что позволяет выполнить более тонкую настройку для нужд разработчика.

И напоследок, стоит напомнить о том, что nonce рекомендуется регулярно обновлять, а не использовать одни и те же данные. Но это уже другая, более широкая тема, которая выходит за рамки этой статьи.

Ссылки

1. Оригинал статьи

Привет. Меня зовут Костя, и я отвечаю за дизайн в AGIMA. Мы занимаемся дизайном интерфейсов. Особенность нашей работы в том, что во многих проектах мы не можем управлять контентом. Например, когда мы делаем какой-нибудь магазин, мы задаем «гнезда», в которые потом система или контент-менеджер вставит фото товаров, цену, описание и т. д. Каталог товаров формируется динамически, а состав главного меню может поменять продакт-оунер после A/B-тестов или хотелок инвестора. Даже надписи на кнопках правит UX-райтер.

В общем, как дизайнеры, мы часто можем контролировать только стили текста, но не сам текст.

В результате я часто устраиваю мини-ликбезы проектной команде, менеджерам и младшим дизайнерам: рассказываю и типографические трюки, и базовые штуки.

Есть некоторые достаточно специфические вопросы, которые приходится обсуждать из года в год. Они все есть в специальной литературе, но кто ж в наше время читает книги. Поэтому я решил собрать всё повторяющееся в коротенькие заметки в одной статье.

Про шрифт DIN

DIN — это известный шрифт, который был разработан в Германии в начале 20-го века. Он получил название от немецкого института стандартов (Deutsches Institut für Normung). Его сделали для использования в технической документации, на дорожных знаках и в прочих утилитарных случаях. Он не устаревший, не современный, он технический (и очень качественный). И использовать его стоит соответствующим образом.

Про длину строки

Оптимальная длина строки 1,5–2,5 алфавита. Или 40–100 символов.

Более длинные строки тяжело читать: глазу приходится пробегать слишком большое расстояние между концом строки и началом следующей. Строки теряются, мысль рвется. Отстой, в общем. Не делайте длинных строк.

В слишком коротких строках мысль часто прерывается на перенос строки, глаза бегают влево-вправо, вместо того чтобы поглощать информацию. Глазная гимнастика вместо чтения. Не делайте коротких строк. Делайте нормальные строки.

Про межстрочное расстояние

Чем длиннее строка, тем сложнее глазу ее не потерять в процессе чтения. Поэтому есть общее правило: чем длиннее строка, тем больше нужно делать межстрочное расстояние.

Оно помогает глазу удерживать строку. Как результат — текст занимает больше места. Поэтому газеты, кстати, набираются в коротенькие колонки: в короткой строке глаз видит и начало, и конец строки, и ему не нужна помощь в виде пустого места между строк. И на страницу влазит просто тонна букв. В книгах издатели могут себе позволить не жадничать, а сделать так, чтобы читать было удобно. Журналы в этой ситуации где-то посередине. Были. В диджитал ограничения и мотивация типографов совсем другие.

Про близость

Не каждая дырка — это воздух, не каждый воздух — это дырка.

Из предыдущей заметки можно понять, что много воздуха между строчками — это не прихоть дизайнера, а эргономическая необходимость. Пустое пространство часто нужно, чтобы управлять вниманием: подчеркнуть какой-то объект, отделить абзац или заголовок, помочь глазу сориентироваться. Например, перед заголовком стоит оставить побольше пространства, чтобы было точно понятно, к чему он относится.

Про точки в заголовках

Точки в заголовках не ставятся. А вот знаки ! ? … — ставятся, потому что они добавляют интонацию или новый смысл.

Но вот вам хорошее правило: если точка добавляет интонацию, то она ставится. 

Например, во фразе «Каждый охотник желает знать, где сидит фазан», если дальше по тексту понятно, что он прямо желает и точка, то «Каждый охотник желает знать, где сидит фазан.».

(Я этого вам не говорил, но вот другое правило: если в конце заголовка хочется добавить «йопта», то точку можно поставить.)

Про кернинг и лигатуры

Когда хороший шрифтовой дизайнер создает шрифт, много времени тратится на кернинг: подготовку буквенных пар. Разные пары букв настраиваются так, чтобы идеально подходить друг к другу. Например, А + V подгоняются так, чтобы не было дырки между ними. 

Иногда в шрифтах две рядом стоящие буквы заменяются на какой-то знак. Это такой шрифтовой понт, не пугайтесь. Называется лигатурой. Часто это очень красиво.

Про разрядку строчных и кражу овец

Если коротко — не увеличивайте межбуквенный интервал, особенно в строчных (маленьких), особенно в текстах для чтения. 

Это снижает удобочитаемость и допустимо только в исключительных случаях. Один из них, кстати, описан ниже. Если ваш дизайнер делает разрядку в строчных, значит, он или ленив и не может найти более элегантного способа добиться выразительности от текста, или способен красть овец. 

Ну, а при чем тут кража овец? В книге «Основы стиля в типографике» Роберт Брингхёрст приводит цитату американского шрифтового дизайнера Фредерика Гауди: «Кто набирает строчными вразрядку, способен красть овец». Впрочем, у этой истории есть второе дно.

Про всякие типографские мелочи для тех, кто молодец

Не буду разводить много текста, просто перечислю то, что нужно знать, если вы приличный дизайнер или хотите унизить понтонуться перед другими дизайнерами своей осведомленностью.

Кавычки-ёлочки

Длинное тире, короткое тире, дефис, минус

Висячие предлоги

Висячая пунктуация

Маюскульные и минускульные цифры

Про бесплатные шрифты

На iOS можно бесплатно использовать и San Francisco, и Roboto.

На Android Roboto можно, а San Francisco нельзя.

На https://fonts.google.com/ куча прекрасных шрифтов бесплатно.

В «Биханс» по словами font free можно раздобыть от обычных до фильдеперсово-специфических шрифтов, в том числе для коммерческого использования.

Пройдитесь по сайтам шрифтовых студий или напишите шрифтовым дизайнерам: многие дают начертания и целые гарнитуры бесплатно или за смешные деньги. Например, нам как-то автор шрифта дал скидку 90% от цены реселлера.

Многие платные шрифты можно заменить на аналог с подходящим характером и качеством без потери качества.

Не воруйте шрифты, это плохо. И дорого, если вас поймают. А я знаю ребят, которые делают автоматизированную систему поиска краденых шрифтов на сайтах.

Про ЗАГЛАВНЫЕ (капс)

Вообще история возникновения заглавных (больших) и строчных (маленьких) букв тянет на отдельную книгу. Например, древние греки тысячи лет назад писали исключительно заглавными. Ещё и без пробелов.

Но сегодня есть консенсус: строчные буквы — это обычный разговор, а заглавные — это крик.

Если вам нужно передать информацию — вы говорите (используете строчные). Если привлечь внимание, подать сигнал — вы кричите или повышаете голос (используете капс).

В начале предложения вы ставите большую букву, потому что это акцент. Какое-то сильное слово (ВНИМАНИЕ!) вы пишете капсом — это привлечение внимания.

Как и в обычном разговоре, если вы будете постоянно кричать на собеседника, ему будет сложно воспринять смысл за эмоцией. Так и в тексте: капс сложно читать и за вашим типографическим криком вы потеряет смысл коммуникации. Вроде всё просто. В общем, не будьте белками-истеричками, используйте капс с умом.

Про разговор

Представьте, что текст — это ваш монолог. Рассказ на публику или приватная беседа. Каждое выделение жирным или италиком — это смена интонации. БОЛЬШИЕ БУКВЫ — ЭТО КРИК. А ещё есть ! и ?.

Как вы будете воспринимать собеседника, который вместо спокойной речи и уместных акцентов постоянно срывается на крик, в одной фразе то повышает, то понижает голос и делает по 4 эффектные паузы за 30 секунд?

Нет, если ваша цель показаться сумасшедшим проповедником, то нет вопросов. Но если ваша коммуникация — это коммуникация уверенного в себе профессионала, то вы будете действовать совершенно по-другому. Проговорите текст вслух, и вы почувствуете, где надо добавить заголовок и какое слово действительно достойно акцента. (Про акценты отдельная заметка.)

Про акценты

Часто вижу желание добавить в текст акценты. И это выделить, и то подсветить. Тут давать капсом, тут болдом, тут шрифт увеличим. Это важно, и это важно… Не могу забыть, как недавно в одном абзаце текста на 50 слов мне оставили 4 комментария «это важно, надо выделить».

В результате получается новая страница от Apple: всё очень нарядное, но ни фига не понятно.

Про акценты II

Выделение жирным очень навязчивое. При сканировании текста его сразу видно. Иногда хорошая стратегия выделить болдом, чтобы читатель мог пролистать весь текст и, выцепляя только то, что выделено болдом, понял суть.

Но часто надо подчеркнуть важность отдельной фразы, не вырывая ее из контекста и не сбивая читателя. Попробуйте в таких случаях чуть изменить цвет текста, сделать небольшую разрядку или использовать Italic.

Подготовили для вас карточки с примерами в нашем телеграм-канале.

Про акценты III

Основная стратегия дизайнеров — уменьшать визуальный шум. Это повышает читабельность и улучшает восприятие текста. А поскольку текст — это чуть ли не основной инструмент продуктового дизайнера, то очень легко скатиться в хаос, пытаясь структурировать, например, карточку товара в екоме или все послания в баннере.

Для новичков есть хорошее правило: на экране не должно быть больше 4 разных стилей. Сюда входят разные начертания, размеры, шрифты и т. д.

Такая аскеза хорошо тренирует умение работать с цветом, композицией, выбирать важное и выделять это воздухом.

Про Дэвида Карсона 

Обычно текст нужен для того, чтобы его читали. Все советы выше в общем-то про это: как сделать так, чтобы было удобно воспринимать информацию через буквы, слова и предложения. Но иногда даже в продуктовом дизайне (а уж в коммуникационном совсем часто) текст нужен не для того, чтобы рассказать про цифры надоев или изменения в правилах декларирования грузов, а ради эмоций. В таком случае текст: буквы, слова, шрифты, пространство и цвет — выполняют не информационную функцию, а декоративную. И важнее то, какую эмоцию он передает, а не информацию. И тогда все правила нарушаются с легкостью. 

Заключение

Работа с текстом — это бездонная тема. В типографике мало железобетонных правил и нерушимых традиций. Много нюансов, мнений и авторитетов. Поэтому любого дизайнера можно зачморить фразой «твоя типографика — говно», а на вопрос «где именно?» можно спокойно ответить: «Это настолько очевидно, что не достойно объяснений».

Но зная общие принципы, думая о цели текста и добавив немного заботы и любви, достаточно просто делать хорошо оформленные тексты.

В общем, делайте хорошо, плохо не делайте, приходите за дизайном к нам в AGIMA.

Если вы давно хотели написать свой эмулятор компьютера, самое время начать. Мы нашли полезную статью, написанную уже давно, но всё ещё актуальную. 

Статья охватывает несколько общих технических вопросов, которые часто задают при написании эмуляторов. Также здесь вы найдёте «схемы» внутреннего устройства эмулятора, которым можно следовать.

Что можно эмулировать?

По сути, всё, что имеет микропроцессор внутри. Конечно, для эмулирования интересны только устройства с более-менее гибкой программой. К ним относятся:

• Компьютеры

• Калькуляторы

• Игровые приставки

• Аркадные игровые автоматы

• и т. д.

Вы можете эмулировать любую компьютерную систему, даже очень сложную (например, компьютер Commodore Amiga). Однако производительность такой эмуляции может оказаться очень низкой.

Что такое «эмуляция» и чем она отличается от «симуляции»?

Эмуляция — это попытка имитировать внутреннюю структуру устройства. Симуляция — это попытка имитировать функции устройства. Например, программа, имитирующая игровой автомат Pacman и запускающая на нем настоящее ПЗУ Pacman, является эмулятором. Игра Pacman, написанная для вашего компьютера, но использующая графику, похожую на настоящую аркаду, является симулятором.

Законно ли эмулировать проприетарное оборудование?

Эмулирование проприетарного оборудования является законным, хоть и находится в «серой» зоне. Главное, чтобы информация для эмулирования была получена законным путем. Также следует знать, что распространение системных ПЗУ (BIOS и т. д.) с помощью эмулятора является незаконным, если они защищены авторским правом.

Три способа создания эмуляции

Есть три основные схемы, которые можно использовать для создания эмулятора. Их можно комбинировать для достижения наилучшего результата.

Интерпретация

Эмулятор байт за байтом считывает эмулируемый код из памяти, декодирует его и исполняет соответствующие команды на эмулируемых регистрах, в памяти и вводе-выводе. Общий алгоритм работы такого эмулятора следующий:

while(CPUIsRunning)  {    Fetch OpCode    Interpret OpCode  }

К достоинствам этой модели относится простота отладки, переносимость и простота синхронизации (вы можете просто подсчитать количество пройденных тактов и привязать к нему остальную часть вашей эмуляции).
Единственный большой и очевидный недостаток — низкая производительность. Интерпретация занимает много ресурсов процессора, так что для нормальной работы потребуется довольно шустрый компьютер. 

Статическая перекомпиляция

Этот метод заключается в следующем: вы берете программу, написанную на эмулированном коде, и пытаетесь перевести ее в код ассемблера вашего компьютера. В результате получится обычный исполняемый файл, который вы сможете запустить на своем компьютере без дополнительного шаманства. Звучит здорово, но это не всегда возможно. Например, вы не можете статически перекомпилировать самомодифицирующийся код, поскольку невозможно сказать, во что он превратится, пока не запустите его. Чтобы избежать неприятных ситуаций, можно попробовать комбинировать статический рекомпилятор с интерпретатором или динамическим перекомпилятором.

Динамическая перекомпиляция

Динамическая перекомпиляция аналогична статической, но происходит во время выполнения программы. Вместо того, чтобы пытаться перекомпилировать весь код сразу, перекомпиляция делается по ходу дела, когда сталкивается с инструкциями CALL или JUMP. Для увеличения скорости этот метод можно комбинировать со статической перекомпиляцией. Подробнее о динамической перекомпиляции можно прочитать в официальном документе Арди, создателя перекомпилирующего эмулятора Macintosh.

Я хочу написать эмулятор. С чего начать?

Чтобы написать эмулятор, вы должны обладать неплохими общими знаниями в области программирования и цифровой электроники. Также очень пригодится опыт программирования на ассемблере.

1. Выберите язык программирования, который будете использовать.

2. Найдите всю доступную информацию об эмулируемом оборудовании.

3. Напишите эмуляцию ЦП или получите существующий код для эмуляции ЦП.

4. Напишите черновой код для эмуляции остального оборудования, хотя бы частично.

5. На этом этапе полезно написать небольшой встроенный отладчик, который позволяет остановить эмуляцию и посмотреть, что делает программа. Также может понадобиться дизассемблер языка ассемблера эмулируемой системы. Напишите свой, если такового нет.

6. Попробуйте запустить программы на вашем эмуляторе.

7. Используйте дизассемблер и отладчик, чтобы увидеть, как программы используют оборудование, и соответствующим образом скорректируйте свой код.

Какой язык программирования мне следует использовать?
Наиболее очевидными являются C и Assembly. Вот плюсы и минусы каждого из них:

Языки ассемблера

+ Как правило, позволяют создавать более быстрый код.

+ Эмуляция регистров ЦП может использоваться для прямого хранения регистров эмулируемого процессора.

+ Многие опкоды можно эмулировать аналогичными опкодами эмулирующего процессора.

— Код не переносимый, т.е. его нельзя запустить на компьютере с другой архитектурой.

— Трудно отлаживать и поддерживать код.

С

+ Код можно сделать переносимым, чтобы он работал на разных компьютерах и операционных системах.

+ Относительно легко отлаживать и поддерживать код.

+ Можно быстро проверить гипотезы о том, как работает реальное оборудование .

— Обычно медленнее, чем чистый ассемблерный код.

Хорошее знание выбранного языка является абсолютной необходимостью для написания работающего эмулятора, так как это довольно сложный проект, и ваш код должен быть оптимизирован для максимально быстрой работы. Не стоит использовать написание компьютерного эмулятора для изучения языка программирования.

Где я могу получить информацию об эмулируемом оборудовании?

Ниже приведен список мест, куда можно заглянуть.

Новостные группы

• comp.emulators.misc
  Это новостная группа для обсуждения компьютерной эмуляции. Её читают многие авторы эмуляторов, хотя много левых обсуждений. Прежде чем публиковать сообщения в этой группе, прочтите FAQ.

• comp.emulators.game-consoles
  То же, что и comp.emulators.misc, но специализируется на эмуляторах игровых консолей. Прежде чем публиковать сообщения в этой группе, прочтите FAQ.

• comp.sys./emulated-system/
  Иерархия comp.sys.* содержит новостные группы, предназначенные для конкретных компьютеров. Вы можете получить много полезной технической информации. Примеры:

comp.sys.msx       MSX/MSX2/MSX2+/TurboR computers

comp.sys.sinclair  Sinclair ZX80/ZX81/ZXSpectrum/QL

comp.sys.apple2    Apple ][

etc.

• alt.folklore.computers

• rec.games.video.classic

FTP

Программирование консолей и игр

Аркадные игровые автоматы

История компьютеров и эмуляции

Сайты

Моя домашняя страница

Репозиторий программирования эмуляции игровых автоматов

Ресурс для программистов эмуляций

Как эмулировать процессор?

Прежде всего, если вам нужно эмулировать стандартный ЦП Z80 или 6502, вы можете использовать один из написанных мной эмуляторов ЦП. Однако для их использования есть определенные условия.

Для тех, кто хочет написать собственное ядро ​​эмуляции ЦП или интересуется, как оно работает, привожу скелет типичного эмулятора ЦП на C. В реальном эмуляторе вы можете пропустить некоторые части и добавить другие самостоятельно.

Counter=InterruptPeriod;  PC=InitialPC;  for(;;)  {    OpCode=Memory[PC++];    Counter-=Cycles[OpCode];    switch(OpCode)    {      case OpCode1:      case OpCode2:      ...    }    if(Counter<=0)    {      /* Check for interrupts and do other */      /* cyclic tasks here                 */      ...      Counter+=InterruptPeriod;      if(ExitRequired) break;    }  }

Во-первых, мы присваиваем начальные значения счетчику циклов процессора (Counter) и счетчику программ (PC):

Counter=InterruptPeriod;  PC=InitialPC;

Counter содержит количество циклов ЦП, оставшихся до следующего предполагаемого прерывания. Обратите внимание, что прерывание не обязательно должно происходить по истечении этого счетчика: вы можете использовать его для многих других целей, таких как синхронизация таймеров или обновление строк развертки на экране. Подробнее об этом позже. 

PC содержит адрес памяти, из которого наш эмулируемый ЦП будет считывать свой следующий код операции.

После присвоения начальных значений запускаем основной цикл:
Обратите внимание, что этот цикл также может быть реализован как

while(CPUIsRunning)  {

где CPUIsRunning — логическая переменная. Это имеет определенные преимущества, так как вы можете прервать цикл в любой момент, установив CPUIsRunning=0. К сожалению, проверка этой переменной на каждом проходе занимает довольно много процессорного времени, и ее следует по возможности избегать. Не реализуйте этот цикл как

while(1)  {

потому что в этом случае некоторые компиляторы будут генерировать код, проверяющий, является ли 1 true или нет. Вы, конечно, не хотите, чтобы компилятор выполнял эту ненужную работу при каждом проходе цикла.

Теперь, когда мы находимся в цикле, первым делом нужно прочитать следующий код операции и изменить счетчик программ:

OpCode=Memory[PC++];

Хотя это самый простой и быстрый способ чтения из эмулируемой памяти, его не всегда получается реализовать. Есть более универсальный способ доступа к памяти.
После получения опкода мы уменьшаем счетчик циклов ЦП на количество циклов, необходимых для этого опкода:

Counter-=Cycles[OpCode];

Таблица Cycles[] должна содержать количество циклов процессора для каждого опкода. Имейте в виду, что некоторые опкоды (например, условные переходы или вызовы подпрограмм) могут занимать разное количество циклов в зависимости от их аргументов. Однако это можно исправить позже в коде.

Теперь пришло время интерпретировать код операции и выполнить его:

switch(OpCode)  {

Есть распространённое заблуждение, что конструкция switch() неэффективна, так как она компилируется в цепочку операторов if() ... else if() ... Это действительно справедливо для конструкций с небольшим количеством операторов, но большие конструкции (100-200 и более операторов) всегда компилируются в таблицу переходов, что делает их весьма эффективными.

Есть два альтернативных способа интерпретации опкодов. Первый — составить таблицу функций и вызвать соответствующую. Этот метод кажется менее эффективным, чем switch(), поскольку есть расходы на вызовы функций. Второй метод заключается в создании таблицы меток и использовании оператора goto. Хотя этот метод немного быстрее, чем switch(), он будет работать только с компиляторами, поддерживающими «предварительно вычисленные метки». Другие компиляторы не позволят вам создать массив адресов меток.

После того, как мы успешно интерпретировали и выполнили опкод, пришло время проверить, нужны ли нам какие-либо прерывания. В этот момент вы также можете выполнять любые задачи, которые необходимо синхронизировать с системными часами:

if(Counter<=0)  {      /* Check for interrupts and do other hardware emulation here */    ...    Counter+=InterruptPeriod;    if(ExitRequired) break;  }

Эти циклические задачи рассматриваются далее в статье.

Обратите внимание, что мы не просто присваиваем Counter=InterruptPeriod, а делаем Counter+=InterruptPeriod: это делает подсчет циклов более точным, так как в Counter могут присутствовать некоторое отрицательное количество циклов.

Также посмотрите на строку

if(ExitRequired) break;

Поскольку проверять выход при каждом проходе цикла слишком ресурсозатратно, мы делаем это только по истечении срока действия Counter: это все равно приведет к выходу из эмуляции, когда вы установите ExitRequired=1, но это не займет столько ресурсов процессора.

Как обрабатывать доступ к эмулируемой памяти?

Самый простой способ получить доступ к эмулируемой памяти — рассматривать ее как простой массив байтов (слов и т. д.). тогда доступ к нему тривиален:

 Data=Memory[Address1]; /* Read from Address1 */   Memory[Address2]=Data; /* Write to Address2  */

Однако такой простой доступ к памяти не всегда возможен по следующим причинам:

• Страничная память
  Адресное пространство может быть фрагментировано на переключаемые страницы. Часто это делается для расширения памяти, когда адресное пространство мало (64 КБ).

• Зеркальная память
  Область памяти может быть доступна по нескольким разным адресам. Например, данные, которые вы записываете в ячейку $4000, также будут отображаться в $6000 и $8000. ПЗУ также могут быть зеркальными из-за неполного декодирования адреса.

• Защита ПЗУ
  Некоторое программное обеспечение на основе картриджей (например, игры MSX) пытается записать в свое собственное ПЗУ и отказывается работать, если запись завершается успешно. Часто это делается для защиты от копирования. Чтобы такое программное обеспечение работало на вашем эмуляторе, вы должны отключить запись в ПЗУ.

• Ввод-вывод с отображением памяти
  В системе могут быть устройства ввода-вывода с отображением памяти. Доступ к таким ячейкам памяти производит «специальные эффекты» и поэтому должен отслеживаться.

Чтобы справиться с этими проблемами, введем пару функций:

Data=ReadMemory(Address1);  /* Read from Address1 */  WriteMemory(Address2,Data); /* Write to Address2  */

Вся специальная обработка, такая как доступ к странице, зеркалирование, обработка ввода-вывода и т. д., выполняется внутри этих функций.

ReadMemory()и WriteMemory()обычно приводят к затратам ресурсов на эмуляцию, потому что они вызываются очень часто. Поэтому они должны быть максимально эффективными. Вот пример этих функций, написанных для доступа к страничному адресному пространству:

static inline byte ReadMemory(register word Address)  {    return(MemoryPage[Address>>13][Address&0x1FFF]);  }  static inline void WriteMemory(register word Address,register byte Value)  {    MemoryPage[Address>>13][Address&0x1FFF]=Value;  }

Обратите внимание на inline. Он заставит компилятор встроить функцию в код, а не вызывать ее. Если ваш компилятор не поддерживает inline или _inline, попробуйте сделать function static: некоторые компиляторы (например, WatcomC) оптимизируют короткие статические функции, встраивая их.

Также имейте в виду, что в большинстве случаев ReadMemory()вызывается в несколько раз чаще, чем WriteMemory(). Поэтому стоит реализовать большую часть кода, WriteMemory(), оставив ReadMemory()как можно более коротким и простым.

Небольшое замечание о зеркалировании памяти:

Как было сказано ранее, многие компьютеры имеют зеркалирование ОЗУ, где значение, записанное в одном месте, появится в других. Хотя эта ситуация может быть обработана в ReadMemory(), обычно это нежелательно, так как ReadMemory() вызывается гораздо чаще, чем WriteMemory(). Более эффективным способом было бы реализовать зеркалирование памяти в функции WriteMemory().

Циклические задачи: что это такое?

Циклические задачи — это задачи, которые должны периодически выполняться на эмулируемой машине, например:

• Обновление экрана

• Прерывания VBlank и HBlank

• Обновление таймеров

• Обновление параметров звука

• Обновление состояния клавиатуры/джойстиков

• и т. д.

Чтобы эмулировать такие задачи, вы должны привязать их к соответствующему количеству циклов процессора. Например, если ЦП должен работать на частоте 2,5 МГц, а дисплей использует частоту обновления 50 Гц (стандарт для видео PAL), прерывание VBlank должно происходить каждые

2500000/50 = 50000 циклов процессора

Теперь, если мы предположим, что весь экран (включая VBlank) имеет высоту 256 строк развертки и 212 из них фактически отображаются на дисплее (т.е. остальные 44 попадают в VBlank), мы получаем, что ваша эмуляция должна обновлять строку развертки каждые

50000/256 ~= 195 циклов процессора

После этого следует сгенерировать прерывание VBlank и ничего не делать, пока мы не закончим с VBlank, т.е.

(256-212)*50000/256 = 44*50000/256 ~= 8594 циклов ЦП

Тщательно рассчитайте количество циклов ЦП, необходимых для каждой задачи, затем используйте их наибольший общий делитель для InterruptPeriod и привяжите к нему все остальные задачи (они не обязательно должны выполняться при каждом истечении срока действия Counter).

Как оптимизировать код C?

Во-первых, за счет выбора правильных опций оптимизации для компилятора можно добиться значительного увеличения производительности кода. Исходя из моего опыта, следующие комбинации дадут вам наилучшую скорость выполнения:

Watcom C++      -oneatx -zp4 -5r -fp3

GNU C++         -O3 -fomit-frame-pointer

Borland C++

Небольшое замечание по поводу развертывания цикла:

Полезной может оказаться опция оптимизатора «раскручивание цикла» (loop unrolling). Эта опция попытается преобразовать короткие циклы в линейные фрагменты кода. Однако мой опыт показывает, что этот вариант не дает никакого прироста производительности. Его включение в некоторых случаях также может привести к поломке вашего кода.

Оптимизация самого кода C немного сложнее, чем выбор параметров компилятора, и обычно зависит от процессора, для которого вы компилируете код. Несколько общих правил применимы ко всем процессорам. Однако не принимайте их за абсолютную истину, поскольку в вашем случае всё может быть иначе:

• Используйте профайлер!
  Запуск вашей программы под управлением приличного профайлера (сразу приходит на ум GPROF) может выявить множество замечательных вещей, о которых вы никогда раньше не подозревали. Вы можете обнаружить, что кажущиеся незначительными фрагменты кода исполняются намного чаще, чем остальная часть, и замедляют работу всей программы. Оптимизация этих фрагментов кода или их переписывание на ассемблере повысит производительность.

• Избегайте C++
  Избегайте использования каких-либо конструкций, которые заставят вас компилировать вашу программу с помощью компилятора C++ вместо простого C: компиляторы C++ обычно добавляют дополнительную нагрузку к сгенерированному коду.

• Размер целых чисел
  Старайтесь использовать только целые числа базового размера, поддерживаемого ЦП, т.е. int единицы , а не short или long. Это уменьшит количество кода, генерируемого компилятором для преобразования между различными длинами целых чисел. Это также может уменьшить время доступа к памяти, поскольку некоторые ЦП работают быстрее всего при чтении/записи данных базового размера.

• Распределение регистров
  Используйте как можно меньше переменных в каждом блоке и объявляйте наиболее часто используемые как register (хотя большинство новых компиляторов могут автоматически помещать переменные в регистры). Это имеет больше смысла для процессоров с большим количеством регистров общего назначения (PowerPC), чем для процессоров с несколькими выделенными регистрами (Intel 80×86).

• Развертывание небольших циклов
  Если у вас есть небольшой цикл, который выполняется несколько раз, всегда полезно вручную развернуть его в линейный фрагмент кода. 

• Сдвиги при умножении/делении
  Всегда используйте сдвиги везде, где вам нужно умножить или разделить на 2^n (J/128==J>>7). Они выполняются быстрее на большинстве процессоров. Кроме того, в таких случаях используйте побитовое И для получения значения по модулю (J%128==J&0x7F).

Что такое низкий/высокий порядок байтов?

Все процессоры обычно делятся на несколько классов в зависимости от того, как они хранят данные в памяти. Хотя есть несколько очень своеобразных экземпляров, большинство процессоров относятся к одному из двух классов:

ЦП с высоким порядком байтов будут хранить данные так, что старшие байты слов всегда будут первыми в памяти. Например, если хранить 0x12345678 на таком процессоре, то память будет выглядеть так:

                      0 1 2 3

                     +—+—+—+—+

                     |12|34|56|78|

                     +—+—+—+—+

Процессоры с низким порядком байтов будут хранить данные так, что младшие байты слов всегда будут первыми в памяти. Пример сверху будет выглядеть на таком процессоре совсем иначе:

                      0 1 2 3

                     +—+—+—+—+

                     |78|56|34|12|

                     +—+—+—+—+

Типичными примерами высокопроизводительных процессоров являются 6809, серия Motorola 680×0, PowerPC и Sun SPARC. К процессорам с низким порядком байтов относятся 6502 и его преемник 65816, Zilog Z80, большинство чипов Intel (включая 8080 и 80×86), DEC Alpha и т. д.

При написании эмулятора вы должны знать порядок байтов обоих процессоров (того, который эмулируем и тот, на котором будет работать эмуляция). Допустим, вы хотите эмулировать процессор Z80 с низким порядком байтов. То есть Z80 хранит свои 16-битные слова младшим байтом вперед. Если для этого использовать процессор с низким порядком байтов (например, Intel 80×86), то все происходит естественным образом. Однако, если вы используете процессор с высоким порядком (PowerPC), внезапно возникает проблема с размещением 16-битных данных Z80 в памяти. Хуже того, если ваша программа должна работать на обеих архитектурах, вам нужен какой-то способ сделать её универсальной.

Один из способов решения проблемы приведен ниже:

typedef union  {    short W;        /* Word access */    struct          /* Byte access... */    {  #ifdef LOW_ENDIAN      byte l,h;     /* ...in low-endian architecture */  #else      byte h,l;     /* ...in high-endian architecture */  #endif    } B;  } word;

Как видите, можно получить доступ к слову как к целому, используя W. Однако каждый раз, когда вашей эмуляции требуется доступ к нему как к отдельным байтам, вы используете B.l и B.h, которые сохраняют порядок.

Если ваша программа будет скомпилирована на разных платформах, нужно проверить, была ли она скомпилирована с правильным порядком, прежде чем исполнять что-либо действительно важное. Вот один из способов выполнить такой тест:

 int *T;    T=(int *)"\01\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";    if(*T==1) printf("This machine is high-endian.\n");    else      printf("This machine is low-endian.\n");

Почему я должен делать программу модульной?

Большинство компьютерных систем состоят из нескольких больших микросхем, каждая из которых выполняет определенную часть системных функций. Таким образом, есть ЦП, видеокарта, звуковая карта. К некоторым из этих микросхем может быть подключена собственная память и другое аппаратное обеспечение.

Типичный эмулятор должен повторять дизайн исходной системы, реализуя функции каждой подсистемы в отдельном модуле. Во-первых, это упрощает отладку, так как все ошибки локализованы в модулях. Во-вторых, модульная архитектура позволяет повторно использовать модули в других эмуляторах. Аппаратное обеспечение компьютера довольно стандартизировано: вы можете найти один и тот же процессор или видеочип во многих разных моделях компьютеров. Гораздо проще эмулировать чип один раз, чем внедрять его снова и снова для каждого компьютера.

Все мы знаем эту историю, когда нужно скопировать какую-нибудь большую структуру, внутри которой множество указателей на другие структуры. Руками это делать лень, поэтому берём какую-нибудь библиотеку и быстро делаем копию. А потом в свободное время решаем проверить, что там с оверхедом.

Меня зовут Егор Гартман, я работаю в бекэнде Авито и я решил протестировать несколько библиотек Deep Copy. А потом сделал свою — быстрее и эффективнее.

Сравнение готовых решений

Для сравнения я выбрал три библиотеки глубокого копирования и два способа копирования через маршалинг:

• github.com/mohae/deepcopy,

• github.com/barkimedes/go-deepcopy,

• github.com/jinzhu/copier,

• json marshal > unmarshal,

• msgpack marshal -> unmarshal.

Критерии отбора были простейшие: 

• звёзды на Github — максимум у Mohae, 

• первая строка выдачи Google — Barkimedes,

• комбайн для копирования, который посоветовали в рабочем чате — Jinzu. 

Все бенчмарки я запускал на своем MacBook Pro 2019 на Core i5. Я использовал простейшую структуру из пяти полей:

type benchSimpleStruct5 struct {   I1 int   F1 float64   S1 string   B1 byte   C1 bool }

Результат получился не отличный, но и не плохой. Практически все испытуемые работают на несколько порядков медленнее прямого копирования:

После я начал менять разные параметры в структуре и измерять оверхед. Во всех графиках ниже на оси Y указан оверхед в секундах, на X — изменяемый параметр. 

Проверил, что будет, если увеличить количество полей. Лучше всего с плоскими структурами из большого числа полей справляется mohae:

Затем стал наращивать уровень вложенности структур. Результат получился такой же — с вложенными структурами лучше справляются библиотеки, а не маршалинг:

Затем проверил, как на оверхед влияет объем данных. Начал с примитивных — обычный массив byte[]: Здесь лучше всего справляются msgpack — работает почти мгновенно даже на большом объёме данных:

И второе измерение оверхеда по объёму данных, только на массиве структур по три поля в каждой. Со структурами ожидаемо лучше справляются библиотеки Deep Copy:

Ещё я тестировал кейс, близкий к реальному при работе с нашей инфомоделью: копировать нетипизированный набор полей, завёрнутый в мапу. Первым был пустой интерфейс map[string]any:

map [string] any {    "int": 1,   "float": 2. ,   "string": "3",   "bytes" make([]byte, 128),   "structs": []*simpleStruct{       {1, 2., "3"},       {1, 2., "3"},       {1, 2., "3"}, }, "nested": map[string]any{ "int": 1, "float": 2. , }, } 

Для такой Map быстрее всего работает маршалинг: msgpack и чуть хуже json. А вот библиотека самая медленная, еще и аллокаций в ней дикое количество:

Второй пример, приближённый к реальности — сложная структура. Это и есть то, ради чего я использовал библиотеки Deep Copy и из-за чего начал их сравнивать.

type complexStructForBench struct {   Int int   Float64 float64   String string    Struct simpleStructBenchmark   Interface barer    PointerToInt *int   PointerToFloat64 *float64   PointerToString *string   PointerToStruct *simpleStructBenchmark    ArrayOfInt [10]int   ArrayOfSimpleStruct [5]simpleStructBenchmark    SliceOfInt []int   SliceOfSimpleStruct []simpleStructBenchmark   SliceOfPtrsToInt []*int   SliceOfStructPtrs []*simpleStructBenchmark }

Здесь msgpack не дал никакого результата, потому что сломалась сериализация интерфейса. Хороший результат по времени показала библиотека, а по оверхеду и аллокациям лучшим стал json.

После всех измерений я пришёл к общему выводу: для эффективного копирования важно знать, что именно копируешь. Немного банально, но это действительно так. 

Сложность копирования будет O{N}, то есть растёт линейно для всех параметров — по времени, памяти, аллокациям. Причём не важно, что именно наращивать при измерении: количество полей или вложенность структур.

Но не всё так хорошо. На каждый int тратится 8 байт дополнительной памяти, а если спрятать его в структуру — то целых 16 байт. Ещё и время копирования по сравнению с прямым растёт на 2 порядка — даже для лучшего по скорости кандидата. Мне хотелось более эффективного копирования.

Сравнение стратегий глубокого копирования

Задачка «сделать эффективную Deep Copy» оказалась не такой уж простой. Напомню, что в Go их 26 типов (про kind of type в предлагаю почитать в документации). Я их разделил на 5 видов по стратегии копирования: 

• примитивные,

• указатели,

• коллекции (Map, слайсы, массивы),

• структуры,

• всё остальное.

Теперь подробнее, как копировать каждый из видов.

Примитивные. Это различные логические, числовые и строковые типы: bool, int, float, complex, string. Их можно копировать как есть.

package main    import (     "fmt"     "unsafe" )  func main() {   var str = "some string"   bptr := unsafe. StringData(str)   *bptr = 'b' // panic: SIGSEGV: segmentation violation    fmt.Println(str) }

Такая строка не является примитивным типом, но её всё равно можно копировать как есть, потому что она всегда read only.

Указатели. Сам по себе указатель скопировать очень легко: создаём копию переменной и затем новый указатель на эту копию. Сложнее, если указатель — это часть структуры.

  type Foo struct {   iptr1 *int   iptr2 *int }  var (   i = int(10)   foo = Foo{&i, &i} )  var (   sliceOfIntPtrs = []*int{&i, &i, &i}   arrayOfIntPtrs = [...]*int{&i, &i, &i}   mapIntToPtr = map[int]*int{1:&i, 2:&i} )

Допустим, что указатели в структуре Foo ссылаются на одну и ту же переменную. Логично, что копия должна сохранять это свойство. Есть кейсы, когда это важно: например, кольцевые ссылки. Контроль ссылок решает проблему с их копированием, это важный и приятный бонус.

К сожалению, не все библиотеки Deep Copy поддерживают такое копирование. Многие сваливаются в panic, если встречают объект с кольцевой ссылкой. 

Коллекции. Здесь особых сложностей нет. Чтобы скопировать Map, нам нужна копия пар «ключ-значение», и новая Map для копии. Для массива так же: копируем элементы и записываем их в новый массив. 

Небольшая сложность возникает только при копировании массивов со слайсами, которые могут ссылаться на одну область памяти.

type strct struct{   Arr [10]int   S1 []int   S2 []int }  var(   arr = [...]int{1,2,3,4,5,6,7,8,10}   s1 := arr[:3]   s2 := arr[5:]    copyMeIfYouCan := strct{   arr, s1, s2   }  ) 

Важно, чтобы копия поддерживала это свойство. Если есть слайсы, которые ссылаются на массив, то при изменении элементов в массиве, они должны меняться и в слайсах. 

Простой Map со ссылками тут не обойтись, потому что слайс ссылается не на underline array, а на первый элемент. Я не смог придумать способ копирования таких массивов, который бы не тянул за собой большой оверхед. Если есть идеи — поделитесь в комментариях.

Структуры. Если все поля в структуре экспортируемые, то их можно просто скопировать по очереди. Для неэкспортируемых полей я протестировал три стратегии: deep copy, shallow copy или просто не копировать их. Выбор стратегии я оставил за пользователем, потому что нужная стратегия зависит от его задачи.

Первая и очевидная стратегия — сделать deep copy всей структуры целиком. В этом случае может возникнуть проблема — одна структура тянет за собой много других. На частном примере структуры Time:

type Time struct {   wall uint64   ext int64    loc *Location }  type Location struct {   name string   zone []zone   tx []zoneTrans    extend string    cacheStart int64   cacheEnd int64   cacheZone *zone } 

В Time есть указатель на другую структуру — Location. А в ней лежат все переходы на зимнее или летнее время, отмены зимнего и переход на постоянное летнее время, изменения часовых поясов и так далее.

Если делать deep copy структуры Time, то придется копировать и всё, что лежит в Location. Это очень долго — время копирования вырастает в сотню раз.

Вторая стратегия — выполнить поверхностную копию (shallow copy). Для структуры Time этот способ подойдёт, но в других случаях может не сработать. 

Третья стратегия — не копировать структуру библиотекой. Тоже вариант для некоторых случаев.

Остальные типы. Сюда я отнёс интерфейсы, функции, каналы и unsafePointer. Для интерфейсов копируем underlying value, а функции и каналы не трогаем. unsafePointer копируем как есть, раз уж автор кода решил добавить его в структуру. Пусть сам с ним и разбирается.

Я тут рассказал совсем немного про сложности в deep copy. Если хотите погрузиться — советую почитать на Github issue с предложением включить Deep Copy в стандартную библиотеку.

После того, как я разобрался с копированием разных типов, осталось оптимизировать библиотеку Deep Copy. 

Моя экспериментальная библиотека Kamino

Свою библиотеку я оптимизировал так, чтобы при глубоком копировании она давала минимальный оверхед. При этом постарался практически не использовать методы unsafe и добавил Generics для простоты использования библиотеки.

В первую очередь я оптимизировал копирование структур. Для этого нужно было сократить количество аллокаций. В лучшей библиотеке с Github их восемь, а я хотел оставить одну.

Какие из них нужные, а какие можно убрать? Одна аллокация выделяется на reflect.Value оригинала, еще одна — для объекта, который будет собственно копией. 

По аллокации выделяется на каждое поле original.Type().Field(i) для сравнения переменной PkgPath с пустой строкой. Эта строка кода проверяет, можно ли экспортировать поле.

В структуре Field есть массив Index, в котором лежит собственно индекс. Этот массив нужен для доступа к вложенным полям методом FieldByIndex. Он позволяет добраться до любого значения в структурах любой вложенности по массиву последовательных индексов.

Причина, почему эта аллокация вообще есть — вызов метода FieldByIndex.  Создатель библиотеки даже оставил в коде комментарий о том, что это единственное решение, которое удалось найти. 

Ещё одна, на мой взгляд, странная аллокация — это cpy.Interface(), которая нужна для преобразования reflect.Value в интерфейс. В ней под капотом происходит повторное копирование содержимого интерфейса, причём сами авторы оставили комментарий, что делать этого не нужно.

Убрать эту аллокацию просто. Нужно использовать метод CanSet() для original. Он проверяет экспортируемость и адресуемость поля. Если этот метод вызывается от оригинала, то он возвращает false. Это справедливо для всех случаев, когда в переменной original — не указатель, то есть, она не адресуемая.

Дальше я решил убрать оставшиеся аллокации. Для этого пришлось вспомнить основы: передача аргумента в функцию, по сути, и есть копирование. То есть, нужно получить адресуемое значение из переданного аргумента.

В нашем случае это будет reflect.Value из копии, в которой мы будем рекурсивно копировать данные при необходимости. Тогда мы получим всего одну аллокацию. Но оказалось, что получить адресуемое reflect.Value не так просто. Я попробовал три метода и корректно работает только последний из них. 

1. Просто передать reflect.ValueOf нельзя — это неадресуемый параметр, и с этим ничего нельзя сделать. 

   func copy(x any) any {   value := reflect.ValueOf(x)    copyNessesaryInplace(value)    return x }

2. Метод reflect.NewAt() под капотом выполняет анбоксинг: разбирает интерфейс any на reflect.Value и указатель на данные. Чтобы получить этот указатель, приходится использовать unsafe, а мне этого не хотелось. 

   func copy(x any) any {     //не тот поинтер     value := reflect.NewAt(reflect.TypeOf(x), unsafe.Pointer(&x))      copyNessesaryInplace(value)      return x }

3. Рабочий способ — использовать указатель на аргумент reflect.ValueOf()

   func copy(x any) any {   value := reflect.ValueOf(&x).Elem()    copyNessesaryInplace(value)    return x }

На этом я закончил оптимизацию структур и перешёл к массивам. Здесь всё очень просто: библиотека аллоцирует память на весь массив и копирует сразу все данные, а затем выполняет Deep Copy, если это необходимо.

Оптимизация Map тоже достаточно простая. Для копирования Map создаю новый Map сразу нужного для копии размера. Для этого есть метод reflect.MakeMapWithSize(). Также, чтобы не плодить лишние аллокации, сразу инициализирую пару key-value и уже ими прохожу по новой Map. 

Для примитивных типов добавил проверки, потому что их можно копировать без Deep Copy и не тратить на них ресурсы. 

Сравнение Kamino и других решений для глубокого копирования

Для тестирования я использовал те же бенчмарки: простая структура с разными параметрами, интерфейс Map и сложная структура. 

На плоских структурах Kamino даёт неплохой результат по оверхеду в зависимости от количества полей:

Оверхед в зависимости от вложенности почти такой же, как у другой библиотеки, но всё-таки чуть лучше:

Оверхед по массиву byte[], результат почти как у предыдущего чемпиона MsgPack:

И оверхед для массива структур []struct тоже довольно неплохой:

На более приближённых к реальности примерах результаты получились очень хорошие. Результат для интерфейса map[string]any : по времени и количеству аллокаций Kamino лучше:

Для сложной структуры результат более показательный. По времени Kamino обогнал самую быструю библиотеку, а по числу аллокаций победил всех:

Библиотека Kamino пока на стадии тестирования, в будущем я буду её дорабатывать и улучшать. Буду рад вашим вопросам и комментариям здесь или на Github.

Предыдущая статья: Как реализовать ролевую систему доступа через Open Policy Agent. Опыт PaaS Авито