dist_cc.c

Go to the documentation of this file.

// #include <m4ri/config.h>
#include <inttypes.h>
#include <strings.h>
#include <stdlib.h>
#include <time.h>
#include <m4ri/m4ri.h>
 
#include "mmio.h"
#include "uthash.h"
#include "util_hash.h"
#include "util_m4ri.h"
#include "util_io.h"
#include "dist_cc.h"

void one_vec_print(const one_vec_t * const pvec){
  printf(" w=%d [ ",pvec->wei);
  for(int i=0; i < pvec->wei; i++)
    printf("%d ",pvec->vec[i]);
  printf("]\n");
}
 
two_vec_t *errors=NULL;

int start_CC_recurs(one_vec_t *err, one_vec_t *urr, one_vec_t * const syn[],
            const int w_limit, const int max_col_wt, 
            const csr_t * const mH, const csr_t * const mHT,
                    params_t * const p){
  const int w=err->wei;
  assert(urr->wei == err->wei);
  int row = syn[w]->vec[0]; 
  const csr_t * const mL = p->spaL;
  int *p_swei = p->swei;
  const int smax = p->smax;
  const int debug = p->debug;
#ifndef NDEBUG  
  if(debug & DBG_LEGACY){
    printf("starting CC recurs w=%d row=%d:\n urr: ",w,row);
    one_vec_print(urr);
    printf(" err: ");
    one_vec_print(err);
    for(int i=0; i <= w; i++){
      printf("# syn[i=%d] ",i);
      one_vec_print(syn[i]);
    }
  }
#endif   
  const int col_min = (p->start_num > 0 && !p->start_scan) ? -1 : urr->vec[0];
  int current_limit = w_limit;
  if (p->min_w != INT_MAX && p->dW >= 0) {
    current_limit = minint(w_limit, p->min_w + p->dW);
  }
  const int syn_w_wei = syn[w]->wei;
  const int rem = current_limit - (w + 1);
  const int max_reach = rem * max_col_wt + (smax > 0 ? smax : 0);
 
  for(int i1 = mH->p[row]; i1 < mH->p[row+1]; i1++){
    const int col = mH->i[i1];
    if(col > col_min){
      const int col_wt = mHT->p[col+1] - mHT->p[col];
      if (w + 1 == current_limit) {
        if (abs(syn_w_wei - col_wt) > (smax > 0 ? smax : 0)) continue;
      } else {
        if (syn_w_wei - col_wt > max_reach) continue;
      }
      int pos = one_ordered_search(err, col);
      if(pos == -1){ 
    urr->vec[w] = col;
    urr->wei++;
#ifndef NDEBUG
    if(debug & DBG_LEGACY){
      printf(" pos=%d urr: ",pos);
      one_vec_print(urr);
    }
#endif  
    pos = one_ordered_ins(err,col);
    syn[w+1]->wei=0;
    int swei = one_csr_row_combine(syn[w+1],syn[w], mHT, col);
    if(debug & DBG_LEGACY){
      printf(" syn: ");
      one_vec_print(syn[w+1]);
    }
    int result = 0;
        if (p->min_w != INT_MAX && p->dW >= 0) {
          current_limit = minint(w_limit, p->min_w + p->dW);
        }
    if (err->wei < current_limit){
      if (swei > 0 && swei <= (current_limit - err->wei) * max_col_wt + (smax > 0 ? smax : 0)){
          result = start_CC_recurs(err,urr,syn,w_limit,max_col_wt,
                       mH,mHT,p);
          if(result == 1)
        return 1;
      }
      // swei == 0 means it is a degenerate vector
      // do not go up in this case 
    }
    else{ // wei >= current_limit
      assert(err->wei == current_limit);
      if(!swei){
        if((!mL) ||  
           (sparse_syndrome_non_zero(mL, err->wei, err->vec))){
          if(debug & DBG_LEGACY){
        printf("swei=%d *** success ***\n",swei);
        one_vec_print(err);
        one_vec_print(syn[w+1]);
          }
              p->codewords = codeword_add_maybe(p, err->vec, err->wei, CW_SRC_OTHER);
              if (codeword_maxc_reached(p)) {
                return 1;
              }
              if (!p->outC && p->maxC == 0) {
                return 1;
              }
        }
      }
      else if(swei <= smax){
        if(debug & DBG_LEGACY){
          printf("# try adding to the hash ewei=%d swei=%d smax=%d p_swei[%d]=%d\n",err->wei,swei,smax,w+1,p_swei[w+1]);
        }
        //      
        errors = hash_add_maybe(syn[w+1],err,errors, p_swei, debug);
      }
    }
    urr->wei--;
    one_ordered_pos_del(err,col,pos);
    if(debug & DBG_LEGACY){
      printf("xerr: ");
      one_vec_print(err);
    }
      }
    }
  }
  if(debug & DBG_LEGACY)
    printf("exiting CC recurs\n\n");
  return 0; 
}

int do_CC_dist(params_t * const p){
  const csr_t * const mH = p->spaH;
  const csr_t * const mL = p->spaL;
  const int wmax = p->wmax;
  const int noscan = p->noscan;
  int *p_swei = p->swei;
  const int smax = p->smax;
  const int debug = p->debug;
 
  const int nvar = mH->cols;
 
  csr_t * const mHT = csr_transpose(NULL,mH);
  csr_dump(stderr, mHT, "HT", debug);
  int max_col_W = csr_max_row_wght(mHT);
  
  one_vec_t *err = calloc(1, sizeof(one_vec_t)+sizeof(int)*wmax);  
  one_vec_t *urr = calloc(1, sizeof(one_vec_t)+sizeof(int)*wmax);  
  one_vec_t **syn = calloc(wmax+1, sizeof(one_vec_t *));
  if((!syn) || (!err) || (!urr))
    ERROR("memory allocation");
  //  err->max = wmax;
  for(int i=0; i <= wmax; i++){
    syn[i]=calloc(1, sizeof(one_vec_t)+sizeof(int)*mH->rows);
    if(!syn[i]) ERROR("i=%d memory allocation",i);
    //    syn[i]->max = mH->rows;    
  }
  int result = 0;
  const int w_start = noscan ? wmax : (p->dmin > 1 ? p->dmin : 1);
  const int d0 = (p->dmin > 1) ? p->dmin : 1;
  const int certified = (w_start <= d0);
  int w_limit_dynamic = wmax;
  if (p->dmax > 0) {
    if (p->outC && p->dW > 0) {
      w_limit_dynamic = minint(wmax > 0 ? wmax : p->dmax + p->dW, p->dmax + p->dW);
    } else {
      w_limit_dynamic = minint(wmax > 0 ? wmax : p->dmax, p->dmax);
    }
  }
  for(int w=w_start; w <= w_limit_dynamic; w++){ /* cluster weight */
    if (p->min_w != INT_MAX && p->dW >= 0) {
      w_limit_dynamic = minint(wmax > 0 ? wmax : p->min_w + p->dW, p->min_w + p->dW);
    }
    if (w > w_limit_dynamic) {
      break;
    }
    int beg, end;
    if (p->start_num > 0) { 
      beg = 0;
      end = p->start_num - 1;
      if(debug & DBG_PROGRESS)
        printf("# recursively searching for w=%d codewords wmax=%d from %d listed start column(s)\n",
               w, wmax, p->start_num);
    }
    else {
      beg = (p->cbeg >= 0) ? p->cbeg : 0;
      end = (p->cend >= 0) ? minint(p->cend, nvar - w) : nvar - w;
      if(debug & DBG_PROGRESS)
        printf("# recursively searching for w=%d codewords wmax=%d beg=%d end=%d\n",w,wmax,beg,end);
    }
    for(int k = beg; k <= end; k++){ /* start column position (or its index in the `start` list) */
      const int i = (p->start_num > 0) ? p->start_list[k] : k;
      err->vec[0] = urr->vec[0] = i;
      err->wei = urr->wei = 1;
      syn[1]->wei=0;
      int swei = one_csr_row_combine(syn[1], syn[0], mHT, i);
      if (w>1){
    if (swei){ 
      result = start_CC_recurs(err,urr,syn,w,max_col_W,mH,mHT,p);
      if(result == 1)
        break;
    }
      }
      else{ // w==1
    if(!swei){  
      if((!mL) ||  
         (sparse_syndrome_non_zero(mL, err->wei, err->vec))){
            p->codewords = codeword_add_maybe(p, err->vec, err->wei, CW_SRC_OTHER);
            if (codeword_maxc_reached(p)) {
              result = 1;
              break;
            }
            if (!p->outC && p->maxC == 0) {
              result = 1;
              break;
            }
      }
    }
    else if(swei <= smax) 
      errors = hash_add_maybe(syn[1],err,errors,p_swei, debug);
      }
      err->wei = urr->wei = 0;
    }
    if(result == 1)
      break;
 
    if (p->min_w > w && w < w_limit_dynamic) {
      printf("-%d\n", w);
      fflush(stdout);
    } else if (p->min_w <= w && p->dW >= 0 && w <= w_limit_dynamic) {
      if (debug & DBG_SUMMARY) {
        fprintf(stderr, "# CC round w=%d finished: searched with dW=%d (min_w=%d, total %lld codewords)\n",
                w, p->dW, p->min_w, p->num_cws);
      }
    }
  }
  
  if(result==1){
    result = err->wei; 
#ifndef NDEBUG
    assert(  0 == sparse_syndrome_non_zero(mH, err->wei, err->vec)); 
    if(mL) assert(sparse_syndrome_non_zero(mL, err->wei, err->vec)); 
#endif     
    if (debug & DBG_CODEWORDS){
      printf("# wmax=%d found cw of weight %d: [",wmax,result);
      int max = ((result<50) || (debug & DBG_LARGE)) ? result : 50 ;
      for(int i=0; i< max; i++)
    printf("%d%s",err->vec[i], i+1!=max?" ": (result==max ? "]\n" : "...]\n"));
    }
  }
  else {
    if (p->min_w <= wmax) {
      result = p->min_w;
    } else if (certified) {
      result = -wmax; 
    } else {
      result = -(d0 - 1); 
    }
  }
 
  if(smax){
    int skipped = 0;
    if (debug & DBG_SUMMARY){
      for(int i=1;i<=wmax; i++) {
        if(p_swei[i] <= mH->rows) {
          printf("# w=%d min non-zero syndrome weight %d\n",i,p_swei[i]);
        } else {
          skipped = 1;
        }
      }
    }
    else{
      printf("# confinement: ");
      for(int i=1;i<=wmax; i++) {
        if(p_swei[i] <= mH->rows) {
          printf("%d%s",p_swei[i],i<wmax?",":"");
        } else {
          skipped = 1;
          printf("?%s",i<wmax?",":"");
        }
      }
      printf("\n");
    }
    if (skipped) {
      printf("# Note: Some weights were skipped in confinement profile. Try increasing smax (current: %d)\n", smax);
    }
  }
  
  for(int i=0; i<= wmax; i++)
    free(syn[i]);
  free(syn);
  free(err);
  free(urr);
  csr_free(mHT);

  two_vec_t *terr, *tmp;
  HASH_ITER(hh, errors, terr, tmp) {
    //    two_vec_print(terr);
    HASH_DEL(errors, terr);
    free(terr);
  }
  
  return result;
}