Fossil

Check-in [3234cf1e]
Login

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

Overview
Comment:On the /hash-collisions page, list the longer collisions with links to /whatid.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:3234cf1efe96ad6d62249f1d7ce02a22d16728a7
User & Date: drh 2015-02-11 12:36:46
Context
2015-02-11
13:18
Fix to the /hash-collisions page: Only consider the SHA1 hashes in the BLOB table, not the random hexadecimal identifiers assigned to tickets and tech-notes. The latter two live in a different namespace. check-in: 327eee14 user: drh tags: trunk
12:36
On the /hash-collisions page, list the longer collisions with links to /whatid. check-in: 3234cf1e user: drh tags: trunk
12:03
On the /hash-collisions page show the true first instance of each collision, not the second. check-in: 4ce3a2bf user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/name.c.

1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075

1076
1077
1078
1079
1080

1081
1082
1083
1084
1085
1086
1087
....
1092
1093
1094
1095
1096
1097
1098




1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112












1113
1114

/*
** WEBPAGE: hash-collisions
**
** Show the number of hash collisions for hash prefixes of various lengths.
*/
void hash_collisions_webpage(void){
  int i;
  int nHash = 0;
  Stmt q;
  char zPrev[UUID_SIZE+1];
  struct {
    int cnt;

    char z[UUID_SIZE+1];
  } aCollide[UUID_SIZE+1];
  login_check_credentials();
  if( !g.perm.Read ){ login_needed(); return; }
  memset(aCollide, 0, sizeof(aCollide));

  memset(zPrev, 0, sizeof(zPrev));
  db_prepare(&q,
      "SELECT tkt_uuid FROM ticket\n"
      "UNION ALL\n"
      "SELECT substr(tagname,7) FROM tag WHERE tagname GLOB 'event-*'\n"
      "UNION ALL\n"
      "SELECT uuid FROM blob\n"
................................................................................
    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 ){
      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("Hash Prefix Collisions");
  @ <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>
  }
  @ </tbody></table>
  @ <p>Total number of hashes: %d(nHash)</p>












  style_footer();
}







|





>





>







 







>
>
>
>








|





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


1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
....
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132

/*
** WEBPAGE: hash-collisions
**
** Show the number of hash collisions for hash prefixes of various lengths.
*/
void hash_collisions_webpage(void){
  int i, kk;
  int nHash = 0;
  Stmt q;
  char zPrev[UUID_SIZE+1];
  struct {
    int cnt;
    Blob ex;
    char z[UUID_SIZE+1];
  } aCollide[UUID_SIZE+1];
  login_check_credentials();
  if( !g.perm.Read ){ login_needed(); return; }
  memset(aCollide, 0, sizeof(aCollide));
  for(i=0; i<ArraySize(aCollide); i++) blob_init(&aCollide[i].ex,0,0);
  memset(zPrev, 0, sizeof(zPrev));
  db_prepare(&q,
      "SELECT tkt_uuid FROM ticket\n"
      "UNION ALL\n"
      "SELECT substr(tagname,7) FROM tag WHERE tagname GLOB 'event-*'\n"
      "UNION ALL\n"
      "SELECT uuid FROM blob\n"
................................................................................
    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 ){
      aCollide[i].cnt++;
      if( aCollide[i].z[0]==0 ) memcpy(aCollide[i].z, zPrev, n+1);
      if( aCollide[i].cnt<25 ){
        blob_appendf(&aCollide[i].ex, " %z%.*s</a>",
           href("%R/whatis/%.*s", i, zPrev), i, zPrev);
      }
    }
    memcpy(zPrev, zUuid, n+1);
  }
  db_finalize(&q);
  style_header("Hash Prefix Collisions");
  @ <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>
  }
  @ </tbody></table>
  @ <p>Total number of hashes: %d(nHash)</p>
  kk = 0;
  for(i=UUID_SIZE; i>=0; i--){
    if( aCollide[i].cnt==0 ) continue;
    if( aCollide[i].cnt>200 ) break;
    kk += aCollide[i].cnt;
    if( aCollide[i].cnt<25 ){
      @ <p>Collisions of length %d(i):
    }else{
      @ <p>First 25 collisions of length %d(i):
    }
    @ %s(blob_str(&aCollide[i].ex))</p>
  }
  style_footer();
}