将Spotify URI编码为Spotify代码

Question

Spotify Codes是一种小条形码，可以让你分享歌曲、艺术家、用户、播放列表等。

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

Spotify根据它们的URI模式生成条形码。此URI spotify:playlist:37i9dQZF1DXcBWIGoYBM5M映射到此条形码：

​

​

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

Answer 1

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

This is a more recent patent

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

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

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 110 110 100 001 110 011 111 011 011 101 000 111。

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

与0-7的灰度表相比，引用包含整数0-9，这意味着使用了使用普通二进制的算法。专利谈到了使用卷积码，然后使用维特比算法进行纠错，所以这可能是它的输出。没有我所相信的状态就不可能再创造的东西。然而，如果你能更好地解释这项专利，我会很感兴趣。

此媒体引用为10位，而其他媒体引用为11或12位。

下面是原始距离的另外两个示例，灰度表二进制，然后是媒体引用：

1.

022673352171662032460

000 011 011 101 100 010 010 111 011 001 100 001 101 101 011 000 010 011 0110 101 000

67775490487

574146602473467556050

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

57639171874

编辑：

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

我还通过代理发现，您可以使用域来获取代码上方的曲目的专辑画面。这表明，Spotify的API和这个scannables 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 )，我想我已经弄清楚了基本的编码过程。然而，基于上面的两个例子，我不相信我从media ref到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矩阵)的乘积。通过将编码函数应用于适当大小的生成器矩阵的每一行，可以从编码函数创建生成器矩阵。例如，将8比特添加到应用于37×37单位矩阵的每行的每个37比特数据向量的CRC函数。

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]