Line data    Source code

       1             : //------------------------------------------------------------------------------
       2             : // LAGraph_Matrix_Hash: generate a single hash value for an entire matrix
       3             : //------------------------------------------------------------------------------
       4             : 
       5             : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
       6             : // SPDX-License-Identifier: BSD-2-Clause
       7             : //
       8             : // For additional details (including references to third party source code and
       9             : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
      10             : // Contributors.txt for a full list of contributors. Created, in part, with
      11             : // funding and support from the U.S. Government (see Acknowledgments.txt file).
      12             : // DM22-0790
      13             : 
      14             : // Contributed by Timothy A. Davis, Texas A&M University
      15             : 
      16             : //------------------------------------------------------------------------------
      17             : 
      18             : #include "LG_internal.h"
      19             : #include <LAGraph.h>
      20             : #include <LAGraphX.h>
      21             : 
      22             : #undef LG_FREE_ALL
      23             : #define LG_FREE_ALL               \
      24             : {                                 \
      25             :     GrB_free(&C);                 \
      26             :     GrB_free(&lg_hash_edge);      \
      27             : }
      28             : 
      29             : #define GOLDEN_GAMMA 0x9E3779B97F4A7C15LL
      30             : 
      31             : // The init function computes a cheesy hash based on splitmix64t
      32       19554 : void LG_HM_hash_edge (uint64_t *z, const uint64_t *x,
      33             :     GrB_Index i, GrB_Index j, const uint64_t *seed)
      34             : {
      35       19554 :     uint64_t result = (i + j * i  + GOLDEN_GAMMA) ;
      36       19554 :     result = (result ^ (*x)) * 0xBF58476D1CE4E5B9LL ;
      37       19554 :     result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9LL ;
      38       19554 :     result = (result ^ (result >> 27)) * 0x94D049BB133111EBLL ;
      39       19554 :     result = (result ^ (result >> 31)) ;
      40       19554 :     (*z) = result ;
      41       19554 : }
      42             : 
      43             : #define HASH_EDGE_DEF \
      44             : "void LG_HM_hash_edge (uint64_t *z, const uint64_t *x,\n"                      \
      45             : "    GrB_Index i, GrB_Index j, const uint64_t *seed)\n"                        \
      46             : "{\n"                                                                          \
      47             : "    uint64_t result = (i + j * i  + 0x9E3779B97F4A7C15LL) ;\n"                \
      48             : "    result = (result ^ (*x)) * 0xBF58476D1CE4E5B9LL ;\n"                      \
      49             : "    result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9LL ;\n"            \
      50             : "    result = (result ^ (result >> 27)) * 0x94D049BB133111EBLL ;\n"            \
      51             : "    result = (result ^ (result >> 31)) ;\n"                                   \
      52             : "    (*z) = result ;\n"                                                        \
      53             : "}\n"
      54             : 
      55         102 : GrB_Info LAGraph_Hash_Matrix(
      56             :     uint64_t *hash,      // [output] hash
      57             :     const GrB_Matrix A,  // matrix to hash
      58             :     char *msg
      59             : ) {
      60             : #if LG_SUITESPARSE_GRAPHBLAS_V10
      61         102 :     GrB_Matrix C = NULL;
      62         102 :     GrB_IndexUnaryOp lg_hash_edge = NULL;
      63             :     GrB_Index nrows, ncols;
      64         102 :     GRB_TRY (GrB_Matrix_nrows(&nrows, A)) ;
      65         102 :     GRB_TRY (GrB_Matrix_ncols(&ncols, A)) ;
      66         102 :     GRB_TRY (GrB_Matrix_new(&C, GrB_UINT64, nrows, ncols)) ;
      67         102 :     GRB_TRY (GxB_IndexUnaryOp_new(
      68             :         &lg_hash_edge, (GxB_index_unary_function) LG_HM_hash_edge,
      69             :         GrB_UINT64, GrB_UINT64, GrB_UINT64, "LG_HM_hash_edge", HASH_EDGE_DEF)) ;
      70             :     
      71             :     // TODO: C takes extra memory which is not nessesary for this computation.
      72             :     // Compute without extra memory if possible.
      73         102 :     GRB_TRY (GrB_Matrix_apply_IndexOp_UINT64(
      74             :         C, NULL, NULL, lg_hash_edge, A, (uint64_t) 0, NULL));
      75         102 :     GRB_TRY (GrB_Matrix_reduce_UINT64(
      76             :         hash, GrB_BXOR_UINT64, GxB_BXOR_UINT64_MONOID, C, NULL)) ;
      77         102 :     LG_FREE_ALL;
      78         102 :     return GrB_SUCCESS;
      79             : #else
      80             :     return GrB_NOT_IMPLEMENTED;
      81             : #endif
      82             : }
      83             : 
      84         102 : GrB_Info LAGraph_Hash_Vector(
      85             :     uint64_t *hash,       // [output] hash
      86             :     const GrB_Vector v,   // Vector to hash
      87             :     char *msg
      88             : ) {
      89             : #if LG_SUITESPARSE_GRAPHBLAS_V10
      90         102 :     return LAGraph_Hash_Matrix(hash, (GrB_Matrix) v, NULL);
      91             : #else
      92             :     return GrB_NOT_IMPLEMENTED;
      93             : #endif
      94             : }