Fossil

Check-in [60af0574]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Expand the /hash-collisions report to show hash prefix collisions on just check-ins in addition to overall hash collisions.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 60af05741590fa9829b321641f4620aa87a0ba4d
User & Date: drh 2015-05-14 18:25:42.819
Context
2015-05-14
18:31
Fix the error output for command-line option errors on the "fossil http" command. ... (check-in: 648dc3e7 user: drh tags: trunk)
18:25
Expand the /hash-collisions report to show hash prefix collisions on just check-ins in addition to overall hash collisions. ... (check-in: 60af0574 user: drh tags: trunk)
16:20
Increase the version number to 1.33. Update the change log. ... (check-in: af872ded user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/name.c.
︙︙
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117

  describe_artifacts_to_stdout("IN (SELECT rid FROM blob WHERE size<0)", 0);
}

/* Maximum number of collision examples to remember */
#define MAX_COLLIDE 25

/*
** WEBPAGE: hash-collisions
**
** Show the number of hash collisions for hash prefixes of various lengths.
*/
void hash_collisions_webpage(void){
  int i, j, kk;
  int nHash = 0;
  Stmt q;
  char zPrev[UUID_SIZE+1];
  struct {
    int cnt;
    char *azHit[MAX_COLLIDE];
    char z[UUID_SIZE+1];
  } aCollide[UUID_SIZE+1];
  login_check_credentials();
  if( !g.perm.Read ){ login_needed(g.anon.Read); return; }
  memset(aCollide, 0, sizeof(aCollide));
  memset(zPrev, 0, sizeof(zPrev));
  db_prepare(&q,"SELECT uuid FROM blob ORDER BY 1");
  while( db_step(&q)==SQLITE_ROW ){
    const char *zUuid = db_column_text(&q,0);
    int n = db_column_bytes(&q,0);
    int i;
    nHash++;
    for(i=0; zPrev[i] && zPrev[i]==zUuid[i]; i++){}
    if( i>0 && i<=UUID_SIZE ){
      if( i>=4 && aCollide[i].cnt<MAX_COLLIDE ){
        aCollide[i].azHit[aCollide[i].cnt] = mprintf("%.*s", i, zPrev);
      }
      aCollide[i].cnt++;
      if( aCollide[i].z[0]==0 ) memcpy(aCollide[i].z, zPrev, n+1);
    }
    memcpy(zPrev, zUuid, n+1);
  }
  db_finalize(&q);
  style_header("SHA1 Prefix Collisions");
  style_submenu_element("Activity Reports", 0, "reports");
  style_submenu_element("Stats", 0, "stat");
  @ <table border=1><thead>
  @ <tr><th>Length<th>Instances<th>First Instance</tr>
  @ </thead><tbody>
  for(i=1; i<=UUID_SIZE; i++){
    if( aCollide[i].cnt==0 ) continue;
    @ <tr><td>%d(i)<td>%d(aCollide[i].cnt)<td>%h(aCollide[i].z)</tr>
  }








|
|
<

|









<
<


|
















<
<
<








1066
1067
1068
1069
1070
1071
1072
1073
1074

1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085


1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104



1105
1106
1107
1108
1109
1110
1111

  describe_artifacts_to_stdout("IN (SELECT rid FROM blob WHERE size<0)", 0);
}

/* Maximum number of collision examples to remember */
#define MAX_COLLIDE 25

/*
** Generate a report on the number of collisions in SHA1 hashes
** generated by the SQL given in the argument.

*/
static void collision_report(const char *zSql){
  int i, j, kk;
  int nHash = 0;
  Stmt q;
  char zPrev[UUID_SIZE+1];
  struct {
    int cnt;
    char *azHit[MAX_COLLIDE];
    char z[UUID_SIZE+1];
  } aCollide[UUID_SIZE+1];


  memset(aCollide, 0, sizeof(aCollide));
  memset(zPrev, 0, sizeof(zPrev));
  db_prepare(&q,"%s",zSql/*safe-for-%s*/);
  while( db_step(&q)==SQLITE_ROW ){
    const char *zUuid = db_column_text(&q,0);
    int n = db_column_bytes(&q,0);
    int i;
    nHash++;
    for(i=0; zPrev[i] && zPrev[i]==zUuid[i]; i++){}
    if( i>0 && i<=UUID_SIZE ){
      if( i>=4 && aCollide[i].cnt<MAX_COLLIDE ){
        aCollide[i].azHit[aCollide[i].cnt] = mprintf("%.*s", i, zPrev);
      }
      aCollide[i].cnt++;
      if( aCollide[i].z[0]==0 ) memcpy(aCollide[i].z, zPrev, n+1);
    }
    memcpy(zPrev, zUuid, n+1);
  }
  db_finalize(&q);



  @ <table border=1><thead>
  @ <tr><th>Length<th>Instances<th>First Instance</tr>
  @ </thead><tbody>
  for(i=1; i<=UUID_SIZE; i++){
    if( aCollide[i].cnt==0 ) continue;
    @ <tr><td>%d(i)<td>%d(aCollide[i].cnt)<td>%h(aCollide[i].z)</tr>
  }
︙︙
1129
1130
1131
1132
1133
1134
1135

























1136
1137

    }
    for(j=0; j<aCollide[i].cnt && j<MAX_COLLIDE; j++){
      char *zId = aCollide[i].azHit[j];
      if( zId==0 ) continue;
      @ %z(href("%R/whatis/%s",zId))%h(zId)</a>
    }
  }

























  style_footer();
}








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156

    }
    for(j=0; j<aCollide[i].cnt && j<MAX_COLLIDE; j++){
      char *zId = aCollide[i].azHit[j];
      if( zId==0 ) continue;
      @ %z(href("%R/whatis/%s",zId))%h(zId)</a>
    }
  }
  for(i=4; i<ArraySize(aCollide); i++){
    for(j=0; j<aCollide[i].cnt && j<MAX_COLLIDE; j++){
      fossil_free(aCollide[i].azHit[j]);
    }
  }
}

/*
** WEBPAGE: hash-collisions
**
** Show the number of hash collisions for hash prefixes of various lengths.
*/
void hash_collisions_webpage(void){
  Stmt q;
  login_check_credentials();
  if( !g.perm.Read ){ login_needed(g.anon.Read); return; }
  style_header("SHA1 Prefix Collisions");
  style_submenu_element("Activity Reports", 0, "reports");
  style_submenu_element("Stats", 0, "stat");
  @ <h1>Hash Prefix Collisions on Check-ins</h1>
  collision_report("SELECT (SELECT uuid FROM blob WHERE rid=objid)"
                   "  FROM event WHERE event.type='ci'"
                   " ORDER BY 1");
  @ <h1>Hash Prefix Collisions on All Artifacts</h1>
  collision_report("SELECT uuid FROM blob ORDER BY 1");
  style_footer();
}