#include "encoder.h"
#include "encoderlib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
short m[64];
ll sm[16];
//combinaciones
ll C(int n, int r){
ll ret=1,dw=1;
for(ll i=2;i<=r;i++) dw*=i;
for(ll i=n-r+1;i<=n;i++){
ll g=gcd(i,dw);
dw/=g;
ret*=i/g;
}
return ret;
}
short multi[21],mid=0;
//encodear con combinaciones
void enc(int len, short ele, ll rnk){
//ele:elemento
if(len==0) return;
//busco el elemento mas pequeño posible
while(rnk>=C(15-ele+len-1,15-ele)){
rnk-=C(15-ele+len-1,15-ele);
ele++;
}
multi[mid++]=ele;//guarda el elemento
enc(len-1,ele,rnk);//proceso lo demas
}
//SD:send data
void SD(int prf,ll msg){
int len=0;
//determino cuantos mensaje necesito
while(msg>=C(16+len,16)) len++;
if(len==0) return;
msg-=C(15+len,16);//ajusto el idx
mid=0;
enc(len,0,msg);//convierto el numero a combinacion
//envio cada elemento con prefijo
for(int i=0;i<len;i++) send(prf|multi[i]);
}
void encode(int N, int M[]){
for(int i=0;i<N;i++) m[i]=M[i];
//divido los datos en grupos de 4 bytes(32 bits)
for(int id=0;id*4<N;id++){
int st=id*4;
sm[id]=0;
//combino 4 numeros de 8 bits en 32 bits
for(int j=st+3;j>=st;j--) sm[id]=(sm[id]<<8)|m[j];
SD(id<<4,sm[id]);
}
}
#include "decoder.h"
#include "decoderlib.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
short M[64];
vector<int>ele[16];
ll SM[16];
ll c(int n, int r){
ll ret=1,dw=1;
for(ll i=2;i<=r;i++) dw*=i;
for(ll i=n-r+1;i<=n;i++){
ll g=gcd(i,dw);
dw/=g;
ret*=i/g;
}
return ret;
}
//decodificacion combinatoria1
void DC(int id){
SM[id]=0;
if(ele[id].empty()) return;
int len=ele[id].size();
SM[id]=c(15+len,16);
sort(ele[id].begin(),ele[id].end());
int prf=0;
for(int cur:ele[id]){
len--;
while(prf<cur){
SM[id]+=c(15-prf+len,15-prf);
prf++;
}
}
return;
}
//mensage : [PPP VVV]
// PPP:prefijo, VVV:valor
//cada mensaje tiene 4 bits superiores e inferiores,
//superiores:ID del grupo
//inferiores:valor del elemento de la combinacion
void decode(int N, int L, int X[]){
for(int i=0;i<16;i++) ele[i].clear();
for(int i=0;i<L;i++) ele[X[i]>>4].push_back(X[i]&15);//agrupo por prefijo
for(int id=0;id<16;id++){
DC(id);
//extraccion de los 4 numeros orginales1
for(int i=(id<<2);i<=((id<<2)|3);i++){
M[i]=(SM[id]&255);//extraer byte por byte
SM[id]>>=8;
}
}
for(int i=0;i<N;i++)output(M[i]);
}
//combinatorio que uso , combinaciones con repeticion
//C(n+r-1,r)
/**
EJ
num:1000
encoder:
supongamos que los comvierte a [3,7]
enviamos dos mensajes:(pref|3) y (pref|7)
nota:con OR concateno
decoder:
recibe [3,7]
los ordena(ya estan ordenados de menor a mayor)
recontruye el numero:C(15+2,16)+C(15-0+1,15-0)+...
con esto se obtiene 1000 de nuevo
**/
