将 Spotify URI 编码为 Spotify 代码

Question

Spotify 代码是小条码，可让您共享歌曲、艺术家、用户、播放列表等。

它们在“条”的不同高度对信息进行编码。23 个条形可以有 8 个离散的高度，这意味着 8^23 个不同的可能条形码。

Spotify 根据其 URI 模式生成条形码。这个 URIspotify:playlist:37i9dQZF1DXcBWIGoYBM5M被映射到这个条形码：

URI 中包含的信息 (62^22) 比代码多得多。您将如何将 URI 映射到条形码？似乎您不能简单地直接对 URI 进行编码。有关更多背景，请参阅我对此问题的“回答”：https : //stackoverflow.com/a/62120952/10703868

Answer 1

该专利解释了一般过程，这是我发现的。

这是最近的专利

使用 Spotify 代码生成器时，网站会向https://scannables.scdn.co/uri/plain/[format]/[background-color-in-hex]/[code-color-in-text]/发出请求[大小]/[spotify-URI]。

使用 Burp Suite，当通过 Spotify 扫描代码时，该应用程序向 Spotify 的 API 发送请求：https : //spclient.wg.spotify.com/scannable-id/id/ [CODE] ? format =json其中 [CODE] 是您正在寻找的媒体参考。此请求可以通过 python 发出，但只能使用通过应用程序生成的 [TOKEN]，因为这是获得正确范围的唯一方法。应用令牌将在大约半小时后到期。

import requests

head={
"X-Client-Id": "58bd3c95768941ea9eb4350aaa033eb3",
"Accept-Encoding": "gzip, deflate",
"Connection": "close",
"App-Platform": "iOS",
"Accept": "*/*",
"User-Agent": "Spotify/8.5.68 iOS/13.4 (iPhone9,3)",
"Accept-Language": "en",
"Authorization": "Bearer [TOKEN]", 
"Spotify-App-Version": "8.5.68"}

response = requests.get('https://spclient.wg.spotify.com:443/scannable-id/id/26560102031?format=json', headers=head)

print(response)
print(response.json())

返回：

<Response [200]>
{'target': 'spotify:playlist:37i9dQZF1DXcBWIGoYBM5M'}

所以 26560102031 是您播放列表的媒体参考。

该专利指出，首先检测到代码，然后可能使用格雷表将其转换为 63 位。例如 361354354471425226605 被编码为 010 101 001 010 111 110 010 111 110 110 100 001 110 011 111 011 011 10 10 10 10 10

但是发送到 API 的代码是 6875667268，我不确定媒体引用是如何生成的，但这是查找表中使用的数字。

参考包含整数 0-9，与 0-7 的灰色表相比，这意味着使用了使用普通二进制的算法。该专利谈到使用卷积码，然后使用维特比算法进行纠错，因此这可能是其输出。如果没有我相信的状态，就不可能重新创造一些东西。但是，如果您能更好地解释该专利，我会很感兴趣。

该媒体引用是 10 位数字，但其他媒体引用是 11 或 12 位。

这是原始距离的另外两个示例，灰度表二进制和媒体参考：

1.

022673352171662032460

000 011 011 101 100 010 010 111 011 001 100 001 101 101 011 000 010 011 110 101 000

67775490487

2. 574146602473467556050

111 100 110 001 110 101 101 000 011 110 100 010 110 101 100 111 111 101 000 111 000

57639171874

编辑：

一些额外信息：网上有一些帖子描述了如何将任何文本（例如 spotify:playlist:HelloWorld）编码为代码，但是这不再有效。

我还通过代理发现您可以使用域来获取代码上方曲目的专辑封面。这表明 Spotify 的 API 和这个可扫描的 url 比以前想象的更紧密地集成在一起。因为它不仅存储 URI 及其代码，还可以验证 URI 并返回更新的专辑封面。

https://scannables.scdn.co/uri/800/spotify%3Atrack%3A0J8oh5MAMyUPRIgflnjwmB

Answer 2

您的怀疑是正确的 - 他们正在使用查找表。对于所有有趣的技术细节，相关专利可在此处获得：https : //data.epo.org/publication-server/rest/v1.0/publication-dates/20190220/patents/EP3444755NWA1/document.pdf

Answer 3

非常有趣的讨论。一直对条形码很感兴趣，所以我不得不看一下。我单独对条形码进行了一些分析（没有访问媒体参考的 API），并且认为我已经弄清楚了基本的编码过程。然而，根据上面的两个例子，我不相信我有从媒体引用到 37 位向量的正确映射（即它适用于情况 2，但不适用于情况 1）。无论如何，如果你还有几对，那么最后一部分应该很容易解决。让我知道。

想要弄清楚这一点的人请不要阅读下面的剧透！

事实证明，该专利中概述的基本过程是正确的，但缺乏细节。我将使用上面的例子总结如下。我实际上对此进行了反向分析，这就是为什么我认为代码描述基本上是正确的，除了步骤（1）之外，即我生成了 45 个条形码，并且所有匹配的条形码都有此代码。

1. Map the media reference as integer to 37 bit vector. 
Something like write number in base 2, with lowest significant bit 
on the left and zero-padding on right if necessary. 
   57639171874 -> 0100010011101111111100011101011010110

2. Calculate CRC-8-CCITT, i.e. generator x^8 + x^2 + x + 1
   The following steps are needed to calculate the 8 CRC bits:

   Pad with 3 bits on the right:
   01000100 11101111 11110001 11010110 10110000
   Reverse bytes:
   00100010 11110111 10001111 01101011 00001101
   Calculate CRC as normal (highest order degree on the left):
   -> 11001100
   Reverse CRC:
   -> 00110011
   Invert check:
   -> 11001100
   Finally append to step 1 result:
   01000100 11101111 11110001 11010110 10110110 01100

3. Convolutionally encode the 45 bits using the common generator
polynomials (1011011, 1111001) in binary with puncture pattern 
110110 (or 101, 110 on each stream). The result of step 2 is 
encoded using tail-biting, meaning we begin the shift register 
in the state of the last 6 bits of the 45 long input vector. 

  Prepend stream with last 6 bits of data:
  001100 01000100 11101111 11110001 11010110 10110110 01100
  Encode using first generator:
  (a) 100011100111110100110011110100000010001001011
  Encode using 2nd generator:
  (b) 110011100010110110110100101101011100110011011
  Interleave bits (abab...):
  11010000111111000010111011110011010011110001...
  1010111001110001000101011000010110000111001111
  Puncture every third bit:
  111000111100101111101110111001011100110000100100011100110011

4. Permute data by choosing indices 0, 7, 14, 21, 28, 35, 42, 49, 
56, 3, 10..., i.e. incrementing 7 modulo 60. (Note: unpermute by 
incrementing 43 mod 60).

  The encoded sequence after permuting is
  111100110001110101101000011110010110101100111111101000111000

5. The final step is to map back to bar lengths 0 to 7 using the
gray map (000,001,011,010,110,111,101,100). This gives the 20 bar 
encoding. As noted before, add three bars: short one on each end 
and a long one in the middle. 

更新：我添加了一个条形码（级别）解码器（假设没有错误）和一个遵循上述描述的备用编码器，而不是等效的线性代数方法。希望这更清楚一点。

更新 2：删除了大部分硬编码数组以说明它们是如何生成的。

线性代数方法定义了线性变换 (spotify_generator) 和掩码，以将 37 位输入映射到 60 位卷积编码数据。掩码是 8 位反转 CRC 卷积编码的结果。Spotify_generator 是一个 37x60 矩阵，它实现了 CRC（37x45 矩阵）和卷积码（45x60 矩阵）生成器的乘积。您可以通过将函数应用于适当大小的生成矩阵的每一行，从编码函数创建生成矩阵。例如，CRC 函数将 8 位添加到应用于 37x37 单位矩阵每行的每个 37 位数据向量。

import numpy as np
import crccheck


# Utils for conversion between int, array of binary
# and array of bytes (as ints)
def int_to_bin(num, length, endian):
    if endian == 'l':
        return [num >> i & 1 for i in range(0, length)]
    elif endian == 'b':
        return [num >> i & 1 for i in range(length-1, -1, -1)]

def bin_to_int(bin,length):
    return int("".join([str(bin[i]) for i in range(length-1,-1,-1)]),2)

def bin_to_bytes(bin, length):
    b = bin[0:length] + [0] * (-length % 8)
    return [(b[i]<<7) + (b[i+1]<<6) + (b[i+2]<<5) + (b[i+3]<<4) + 
        (b[i+4]<<3) + (b[i+5]<<2) + (b[i+6]<<1) + b[i+7] for i in range(0,len(b),8)]
    
# Return the circular right shift of an array by 'n' positions    
def shift_right(arr, n):
    return arr[-n % len(arr):len(arr):] + arr[0:-n % len(arr)]

gray_code = [0,1,3,2,7,6,4,5]
gray_code_inv = [[0,0,0],[0,0,1],[0,1,1],[0,1,0],
                 [1,1,0],[1,1,1],[1,0,1],[1,0,0]]

# CRC using Rocksoft model: 
# NOTE: this is not quite any of their predefined CRC's
# 8: number of check bits (degree of poly)
# 0x7: representation of poly without high term (x^8+x^2+x+1)
# 0x0: initial fill of register
# True: byte reverse data
# True: byte reverse check
# 0xff: Mask check (i.e. invert)
spotify_crc = crccheck.crc.Crc(8, 0x7, 0x0, True, True, 0xff)

def calc_spotify_crc(bin37):
    bytes = bin_to_bytes(bin37, 37)
    return int_to_bin(spotify_crc.calc(bytes), 8, 'b')

def check_spotify_crc(bin45):
    data = bin_to_bytes(bin45,37)
    return spotify_crc.calc(data) == bin_to_bytes(bin45[37:], 8)[0]

# Simple convolutional encoder
def encode_cc(dat):
    gen1 = [1,0,1,1,0,1,1]
    gen2 = [1,1,1,1,0,0,1]
    punct = [1,1,0]
    dat_pad = dat[-6:] + dat # 6 bits are needed to initialize
                             # register for tail-biting
    stream1 = np.convolve(dat_pad, gen1, mode='valid') % 2
    stream2 = np.convolve(dat_pad, gen2, mode='valid') % 2
    enc = [val for pair in zip(stream1, stream2) for val in pair]
    return [enc[i] for i in range(len(enc)) if punct[i % 3]]
    
# To create a generator matrix for a code, we encode each row
# of the identity matrix. Note that the CRC is not quite linear
# because of the check mask so we apply the lamda function to
# invert it. Given a 37 bit media reference we can encode by
#     ref * spotify_generator + spotify_mask (mod 2)
_i37 = np.identity(37, dtype=bool)
crc_generator = [_i37[r].tolist() + 
          list(map(lambda x : 1-x, calc_spotify_crc(_i37[r].tolist())))
          for r in range(37)]
spotify_generator = 1*np.array([encode_cc(crc_generator[r]) for r in range(37)], dtype=bool)  
del _i37

spotify_mask = 1*np.array(encode_cc(37*[0] + 8*[1]), dtype=bool) 
    
# The following matrix is used to "invert" the convolutional code.
# In particular, we choose a 45 vector basis for the columns of the
# generator matrix (by deleting those in positions equal to 2 mod 4)
# and then inverting the matrix. By selecting the corresponding 45 
# elements of the convolutionally encoded vector and multiplying 
# on the right by this matrix, we get back to the unencoded data,
# assuming there are no errors.
# Note: numpy does not invert binary matrices, i.e. GF(2), so we
# hard code the following 3 row vectors to generate the matrix.
conv_gen = [[0,1,0,1,1,1,1,0,1,1,0,0,0,1]+31*[0],
            [1,0,1,0,1,0,1,0,0,0,1,1,1] + 32*[0],
            [0,0,1,0,1,1,1,1,1,1,0,0,1] + 32*[0] ]

conv_generator_inv = 1*np.array([shift_right(conv_gen[(s-27) % 3],s) for s in range(27,72)], dtype=bool) 


# Given an integer media reference, returns list of 20 barcode levels
def spotify_bar_code(ref):
    bin37 = np.array([int_to_bin(ref, 37, 'l')], dtype=bool)
    enc = (np.add(1*np.dot(bin37, spotify_generator), spotify_mask) % 2).flatten()
    perm = [enc[7*i % 60] for i in range(60)]
    return [gray_code[4*perm[i]+2*perm[i+1]+perm[i+2]] for i in range(0,len(perm),3)]
    
# Equivalent function but using CRC and CC encoders.
def spotify_bar_code2(ref):
    bin37 = int_to_bin(ref, 37, 'l')
    enc_crc = bin37 + calc_spotify_crc(bin37)
    enc_cc = encode_cc(enc_crc)
    perm = [enc_cc[7*i % 60] for i in range(60)]
    return [gray_code[4*perm[i]+2*perm[i+1]+perm[i+2]] for i in range(0,len(perm),3)]
    
# Given 20 (clean) barcode levels, returns media reference
def spotify_bar_decode(levels):
    level_bits = np.array([gray_code_inv[levels[i]] for i in range(20)], dtype=bool).flatten()
    conv_bits = [level_bits[43*i % 60] for i in range(60)]
    cols = [i for i in range(60) if i % 4 != 2] # columns to invert
    conv_bits45 = np.array([conv_bits[c] for c in cols], dtype=bool)
    bin45 = (1*np.dot(conv_bits45, conv_generator_inv) % 2).tolist()
    if check_spotify_crc(bin45):
        return bin_to_int(bin45, 37)
    else:
        print('Error in levels; Use real decoder!!!')
        return -1

例子：

>>> levels = [5,7,4,1,4,6,6,0,2,4,3,4,6,7,5,5,6,0,5,0]
>>> spotify_bar_decode(levels)
57639171874
>>> spotify_barcode(57639171874)
[5, 7, 4, 1, 4, 6, 6, 0, 2, 4, 3, 4, 6, 7, 5, 5, 6, 0, 5, 0]