Encodage de l'URI Spotify en codes Spotify

Votre suspicion était correcte - ils utilisent une table de consultation. Pour tous les détails techniques amusants, le brevet correspondant est disponible ici: https://data.epo.org/publication-server/rest/v1.0/publication-dates/20190220/patents/EP3444755NWA1/document.pdf

Le brevet explique le processus général, c'est ce que j'ai trouvé.

Ceci est un brevet plus récent

Lors de l'utilisation du générateur de code Spotify, le site Web fait une demande à https://scannables.scdn.co/uri/plain/[formatedral/[background-color-in-hexedral/[code-color-in-textITED/ [taille] / [spotify-URI] .

À l'aide de Burp Suite, lors de la numérisation d'un code via Spotify, l'application envoie une requête à l'API de Spotify: https://spclient.wg.spotify.com/scannable-id/id/[CODE unity?format= json où [CODE] est le référence médiatique que vous recherchiez. Cette requête peut être effectuée via python mais uniquement avec le [TOKEN] qui a été généré via l'application car c'est le seul moyen d'obtenir la bonne portée. Le jeton d'application expire dans environ une demi-heure.

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

Qui retourne:

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())

Donc 26560102031 est la référence média pour votre playlist.

Le brevet déclare que le code est d'abord détecté puis éventuellement converti en 63 bits à l'aide d'une table de Gray. Par exemple, 361354354471425226605 est codé dans 010 101 001 010 111 110 010 111 110 110 100 001110 011 111 011 011 101 101 000 111.

Cependant, le code envoyé à l'API est 6875667268, je ne sais pas comment la référence multimédia est générée, mais c'est le numéro utilisé dans la table de recherche.

La référence contient les entiers 0-9 par rapport à la table grise de 0-7 impliquant qu'un algorithme utilisant le binaire normal a été utilisé. Le brevet parle de l'utilisation d'un code convolutif, puis de l'algorithme de Viterbi pour la correction d'erreur, donc cela peut être le résultat de cela. Quelque chose d'impossible à recréer sans les états que je crois. Cependant, je serais intéressé si vous pouviez mieux interpréter le brevet.

Cette référence multimédia comporte 10 chiffres, mais d'autres en ont 11 ou 12.

Voici deux autres exemples des distances brutes, le binaire de la table grise, puis la référence multimédia:

1.

022673352171662032460

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

67775490487

2. 574146602473467556050

111100110001 11010110100000111101001011010110011111111101000111000

57639171874

Éditer:

Quelques informations supplémentaires: il y a quelques articles en ligne décrivant comment vous pouvez encoder n'importe quel texte tel que spotify: playlist: HelloWorld dans un code mais cela ne fonctionne plus.

J'ai également découvert via le proxy que vous pouvez utiliser le domaine pour récupérer la pochette d'album d'une piste au-dessus du code. Cela suggère une intégration plus étroite de l'API de Spotify et de cette URL numérisable qu'on ne le pensait auparavant. Comme il stocke non seulement les URI et leurs codes, mais peut également valider les URI et renvoyer la pochette d'album mise à jour.

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

Discussion très intéressante. J'ai toujours été attiré par les codes à barres, j'ai donc dû y jeter un coup d'œil. J'ai fait une analyse des codes à barres seuls (je n'ai pas accédé à l'API pour les références multimédias) et je pense avoir compris le processus de codage de base. Cependant, sur la base des deux exemples ci-dessus, je ne suis pas convaincu que le mappage de la référence multimédia au vecteur 37 bits est correct (c'est-à-dire que cela fonctionne dans le cas 2 mais pas dans le cas 1). En tout cas, si vous avez quelques paires de plus, cette dernière partie devrait être simple à élaborer. Faites le moi savoir.

Pour ceux qui veulent comprendre cela, ne lisez pas les spoilers ci-dessous!

Il s'avère que le processus de base décrit dans le brevet est correct, mais manque de détails. Je vais résumer ci-dessous en utilisant l'exemple ci-dessus. En fait, j'ai analysé cela à l'envers, c'est pourquoi je pense que la description du code est fondamentalement correcte, sauf pour l'étape (1), c'est-à-dire que j'ai généré 45 codes à barres et tous les codes correspondants avaient ce code.

>>> 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]

MISE À JOUR: J'ai ajouté un décodeur de code à barres (niveaux) (en supposant qu'aucune erreur) et un autre encodeur qui suit la description ci-dessus plutôt que la méthode d'algèbre linéaire équivalente. Espérons que ce soit un peu plus clair.

La méthode d'algèbre linéaire définit la transformation linéaire (spotify_generator) et le masque pour mapper l'entrée de 37 bits dans les données codées par convolution de 60 bits. Le masque résulte du codage par convolution du CRC inversé 8 bits. Le spotify_generator est une matrice 37x60 qui implémente le produit des générateurs pour le CRC (une matrice 37x45) et les codes convolutifs (une matrice 45x60). Vous pouvez créer la matrice de générateur à partir d'une fonction d'encodage en appliquant la fonction à chaque ligne d'une matrice de générateur de taille appropriée. Par exemple, une fonction CRC qui ajoute 8 bits à chaque vecteur de données de 37 bits appliqué à chaque ligne d'une matrice d'identité 37x37.

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)]


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]]
    
    
    
# This 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.
conv_generator_inv_compact = [1218965405696, 1946962362368, 2742336618496, 
                             9751723245568, 15575698898944, 21938692947968, 
                             7645041786882, 19052474925059, 34772055228420, 
                             25975962206225, 11682311045148, 31885837205543, 
                             31885837205645, 23089744183522, 8796093022527, 
                             8796093023343, 8796093024021, 2554, 9082, 14506, 
                             20432, 72656, 116048, 163456, 581248, 928384, 
                             1307648, 4649984, 7427072, 10461184, 37199872, 
                             59416576, 83689472, 297598976, 475332608, 
                             669515776, 2380791808, 3802660864, 5356126208, 
                             19046334464, 30421286912, 42849009664, 
                             152370675712, 243370295296, 342792077312]
                             
conv_generator_inv = 1*np.array([int_to_bin(conv_generator_inv_compact[i], 45, 'l') for i in range(45)], dtype=bool)


spotify_generator_compact = [281474976710656979, 571957152676054446, 660903245316622432,
                             915356624263068669, 677791743919282035, 67553994410594031,
                             810647932926935004, 66428094504072325, 979532918953666571,
                             265712378018787389, 990791918027227226, 684547143369654461,
                             967148020040663151, 601230550345449695, 890586826461937795,
                             356910271474696243, 133982090378084457, 114841792888701138,
                             998673233458757808, 1149543828307312735, 1146166143417843893,
                             692428700137816151, 799389308594159757, 782501047288463365,
                             1130018780479499, 47293791861735486, 103592583954956380,
                             18080300487671984, 931215155348373596, 241099260471279795,
                             26950129508417626, 764895055071674558, 460748148596277251,
                             316360281636732934, 173177479421231118, 454441349899354166,
                             450078487760339044]

spotify_generator = 1*np.array([int_to_bin(spotify_generator_compact[i], 60, 'l') for i in range(37)], dtype=bool)

spotify_mask = np.array([0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 
                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                         1, 1, 0, 1, 0, 1, 0, 0, 1, 1], 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

Et exemple:

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.