Как работают коды Spotify?

Коды Spotify ^[1] подобны QR-кодам. Их можно генерировать для того, чтобы делиться песнями, исполнителями, плейлистами и пользователями. Я решил разобраться в принципе их действия, в результате чего проделал извилистый путь по истории штрихкодов, патентам, сниффингу пакетов, коррекции ошибок и кодам Грея.

Spotify URI

Начнем со Spotify URI (универсального идентификатора ресурса). У всех медиа элементов (музыкантов, альбомов, песен, плейлистов, пользователей) есть свои URI. К примеру, у песни группы ABBA “Take a Chance on Me” идентификатор следующий:

spotify:track:6vQN2a9QSgWcm74KEZYfDL.

У альбома “The Album” этой же группы он следующий:

spotify:album:5GwbPSgiTECzQiE6u7s0ZN

Как видите, URI можно разбить на составляющие:

spotify:<media type>:<22 characters>.

Эти 22 символа могут включать числа 0-9, знаки a-z и A-Z. Получается, что для каждого символа есть 10 + 26 + 26 = 62 варианта (почти Base64 ^[2]). Поэтому в потенциале количество URI на Spotify может достигать 62²², то есть 2.7e39 или

2,707,803,647,802,660,400,290,261,537,185,326,956,544

Для наглядности приведу сравнение:

x = 62 ** 22
# количество миллисекунд в году
x //= 365 * 24 * 60 * 60 * 1000
# количество слов в Библии (около 1 миллиона)
x //= 1000000

Если запрограммировать Spotify каждую миллисекунду генерировать столько URI, сколько содержится слов в Библии, то программа сможет делать это в течение 85,863,890,404,701,306,452,633 лет. Можно смело сказать, что дефицита идентификаторов на этом ресурсе в ближайшем будущем точно не ожидается.

Что такое штрихкод

Штрихкоды имеют довольно обширную историю ^[3]. На деле существует целый ряд способов кодирования информации в разные штрихкоды.

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

В другой системе ^[4] данные кодируются через цвета:

В QR-кодах ^[5] используется двухмерная матрица точек.

Во многих почтовых штрихкодах кодирование производится посредством вертикальных штрихов различной высоты (например, в интеллектуальном почтовом штрихкоде (IMB ^[6])).

Коды Spotify

Коды Spotify работают подобно IMB — информацию можно сохранять в вертикальных штрихах разной длины.

Вот код Spotify для той же песни ABBA “Take a Chance on Me”:

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

Из этого следует, что данные кодируются в восьмеричной системе ^[7].

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

В функции ниже для вычисления последовательности высот штрихов на основе размера логотипа я использую библиотеку scikit-image ^[8].

from skimage import io
from skimage.measure import label, regionprops
from skimage.filters import threshold_otsu
from skimage.color import rgb2gray


def get_heights(filename: str) -> list:
    """Открывает изображение и возвращает список высот штрихов."""
    # преобразуем в оттенки серого, а затем в двоичный формат
    image = io.imread(filename)
    im = rgb2gray(image)
    binary_im = im > threshold_otsu(im)

    # размечаем связанные области как объекты
    labeled = label(binary_im)

    # получаем размеры и позиции рамки вокруг объектов
    bar_dimensions = [r.bbox for r in regionprops(labeled)]

    # упорядочиваем по X
    bar_dimensions.sort(key=lambda x: x[1], reverse=False)

    # первый объект (логотип spotify) соответствует высоте самого высокого штриха
    logo = bar_dimensions[0]
    max_height = logo[2] - logo[0]
    sequence = []
    for bar in bar_dimensions[1:]:
        height = bar[2] - bar[0]
        ratio = height / max_height
        # умножаем на 8, чтобы получить восьмеричное целое 
        ratio *= 8
        ratio //= 1
        # преобразуем в целое число (и делаем основой 0)
        sequence.append(int(ratio - 1))
    return sequence

Это последовательность кода Spotify для “Take on Me”:

>>> get_heights("/imgs/spotify/spotify_track_6vQN2a9QSgWcm74KEZYfDL.jpg")
[0, 5, 1, 2, 0, 6, 4, 3, 7, 1, 6, 7, 7, 7, 7, 3, 1, 6, 3, 7, 0, 7, 0]

А вот те же результаты, представленные в виде штрихкода:

Рассмотрев несколько штрихкодов, я понял, что первый и последний штрих всегда равны 0, а 12-й всегда 7. Это должно помогать в распознании валидности кода. То, что 12-й штрих всегда является максимальным, также помогает вычислить пропорции высот других штрихов.

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

[0, 3, 3, 0, 5, 2, 2, 2, 2, 5, 1, 7, 0, 0, 5, 6, 0, 7, 7, 7, 1, 5, 0]
    [0, 5, 6, 5, 3, 5, 4, 2, 7, 2, 5, 7, 1, 3, 1, 1, 6, 1, 1, 6, 7, 6, 0]
    [0, 4, 6, 6, 6, 4, 4, 1, 6, 6, 6, 7, 7, 3, 6, 0, 7, 6, 0, 2, 1, 7, 0]
    [0, 0, 3, 3, 7, 5, 2, 3, 1, 1, 4, 7, 5, 5, 5, 3, 3, 7, 5, 1, 4, 3, 0]
    [0, 6, 2, 2, 1, 5, 2, 6, 2, 2, 3, 7, 7, 6, 6, 4, 5, 6, 0, 1, 4, 3, 0]
    [0, 7, 7, 1, 4, 7, 1, 0, 4, 7, 1, 7, 6, 5, 6, 3, 1, 6, 4, 4, 7, 7, 0]
    [0, 1, 1, 1, 5, 7, 1, 3, 3, 1, 0, 7, 7, 0, 7, 3, 2, 3, 0, 6, 0, 0, 0]
    [0, 7, 6, 6, 7, 4, 4, 6, 7, 0, 6, 7, 0, 4, 1, 7, 3, 2, 0, 5, 4, 7, 0]
    [0, 0, 0, 6, 1, 3, 3, 2, 2, 0, 2, 7, 3, 2, 4, 1, 6, 0, 1, 5, 0, 4, 0]

Этот код состоит из 23 штрихов, только 20 из которых фактически несут информацию. Это означает, что в такой код можно закодировать 8²⁰ единиц информации.

Из URI в штрихкод

Как преобразовать 62²²-битный URI в 8²⁰-битный штрихкод? Ведь в нем содержится в 2.3e+21 раз больше информации.

На этом этапе я начал задавать вопросы и искать ответы. Изначально я обратился к участникам StackOverflow с этим вопросом ^[9], но в конечном итоге я задал уже другой ^[10]. На форуме я получил пару ответов, которые вели на релевантные патенты и содержали больше информации о таблице соответствий Spotify.

Вот один патент. ^[11]

Вот еще один более свежий патент. ^[12]

Скажу просто: «Патенты хуже всего». Они чрезвычайно перегружены терминологией. Если раньше я считал, что это в академических работах полно жаргона, то после прочтения нескольких патентов мое мнение изменилось.

Процесс

Когда вы заходите на страницу кодов Spotify и вводите нужный URI, создается «медиа-ссылка». Эта ссылка имеет длину 37 бит и является ключом, связывающим штрихкод с заданным URI. При этом она может быть просто хэшем увеличивающегося индекса.

После извлечения медиа-ссылки из штрихкода нужно сверить ее с базой данных Spotify (таблицей соответствий), чтобы определить, какому URI она соответствует. Один из участников StackOverflow выяснил ^[13], что можно перехватить запрос, выполняемый телефоном при сканировании штрихкода, чтобы определить эту медиа-ссылку и конечную точку API.

heights = [0, 2, 6, 7, 1, 7, 0, 0, 0, 0, 4, 7, 1, 7, 3, 4, 2, 7, 5, 6, 5, 6, 0]
media_reference = "67775490487"
uri = "spotify:user:jimmylavallin:playlist:2hXLRTDrNa4rG1XyM0ngT1"

Для получения из медиа-ссылки кода Spotify и наоборот необходимо проделать несколько шагов.

Циклический контроль избыточности

Для медиа-ссылки выполняется циклический контроль избыточности ^[14]. Исходя из того, что вычисляются при этом 8 бит, я предполагаю, что на Spotify используется CRC8.

import crc8

hash = crc8.crc8()
media_ref = 67775490487
ref_bytes = media_ref.to_bytes(5, byteorder="big")
print(ref_bytes)
# b'x0fxc7xbbxe9xb7'
hash.update(ref_bytes)
check_bits = hash.digest()
print(check_bits)
# b'x0c'
Присоединяем crc к медиа-ссылке:
media_reference = b'x0fxc7xbbxe9xb7x0c'

Упреждающая коррекция ошибок

Далее с помощью упреждающей коррекции ошибок (FEC ^[15]) в код добавляется определенная избыточность. Это повышает надежность процесса декодирования. Декодирование кодов Spotify подразумевает переход от аналоговой формы (высоты штрихов) в цифровую (медиа-ссылка), значит подобная коррекция ошибок будет здесь вполне уместна.

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

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

Полученная тройка	Интерпретирована как
000	                         0 (без ошибок)
001	                         0
010	                         0
100	                         0
111	                         1 (без ошибок)
110	                         1 
101	                         1
011	                         1

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

Spotify добавляет 15 бит к 45-битовому коду, значит скорость потока будет 45/60 = 0.75. Это высокая скорость (близка к 1), что говорит об откровенной слабости этой схемы, в результате чего она обеспечивает ограниченный объем коррекции ошибок. Но это нормально. Вот если вы отправляете сообщение зонду в далеком космосе, тогда потребуется очень сильный код. В случае же со Spotify риски невелики. При декодировании ошибочной медиа-ссылки обращение к серверу можно без проблем повторить.

Общая длина кода после коррекции ошибок составляет 60 бит, что в точности соответствует объему информации, которую можно закодировать в 20 восьмеричных единиц (высот штрихов) штрихкода Spotify.

В патентах упоминается, что на Spotify декодирование прошедшего коррекцию ошибок кода в медиа-ссылку выполняется с помощью алгоритма Витерби ^[16]. Здесь я в него углубляться не стану, скажу лишь, что он находит наиболее вероятную медиа-ссылку, опираясь на избыточные биты.

Код Грея

Эта часть кодов Spotify мне очень нравится.

Код Грея ^[17] – это альтернативный способ представления двоичного числа. Если внимательно посмотреть на приведенную ниже таблицу, то можно увидеть, что код Грея работает путем изменения всего одного бита за раз.

Десятичный	Двоичный	Грей
0	                000	        000
1	                001    	001
2	                010   	011
3	                011   	010
4	                100   	110
5	                101   	111
6	                110   	101
7	                111    	100

Почему на Spotify используется код Грея? Чем разработчиков не устроило стандартное двоичное представление?

Разница между 3 и 4 в коде Грея составляет всего один бит (010 -> 110). В обычном же двоичном представлении эта разница составляет уже 3 бита (100 -> 011). При переходе из аналоговой формы (высота штриха) в двоичную использование кодов Грея сокращает
количество «ошибочных» бит в случае вычисления ошибочной высоты.

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

Меня радует то, как на Spotify используются олдскульные техники компьютерной науки. Работа Фрэнка Грея 1947 года, посвященная функционированию электромеханических переключателей, остается актуальной по сей день. Когда вы находитесь на стыке между аналоговыми и цифровыми технологиями, актуальность обретают многие старые концепции.

Заключение

Изначально я рассчитывал реализовать собственный инструмент преобразования кода Spotify в URI, но в итоге не вышло. Мне не известно, какой именно тип упреждающей коррекции ошибок используется на Spotify. Мне также достоверно неизвестно, используют ли они CRC8.

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

Так что, ожидайте продолжения.

Автор: Дмитрий Брайт

Источник ^[18]