commit bb38219da9141413d874ac0b26bb82ca17881a52
parent 1df71b59bbf393268c88db5036432a16e12c1a47
Author: MTRNord <mtrnord1@gmail.com>
Date: Sun, 25 Feb 2024 01:50:13 +0100
Initial conversion of the python version to a golang version
Diffstat:
| M | .gitignore | | | 3 | +++ |
| A | cmd/scanner.go | | | 91 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | go.mod | | | 15 | +++++++++++++++ |
| A | go.sum | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | helpers/helpers.go | | | 79 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | pdq_hasher.go | | | 549 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | types/hash256.go | | | 237 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
7 files changed, 1029 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -19,3 +19,6 @@
# Go workspace file
go.work
+
+scanner
+blur-a-little.jpg
diff --git a/cmd/scanner.go b/cmd/scanner.go
@@ -0,0 +1,91 @@
+package main
+
+import (
+ "flag"
+ "log"
+ "os"
+ "path/filepath"
+
+ pdq "github.com/MTRNord/pdqhash-go"
+ "github.com/MTRNord/pdqhash-go/types"
+ "github.com/davidbyttow/govips/v2/vips"
+ "github.com/h2non/filetype"
+)
+
+// This is an example. It is not meant to be run in prod.
+
+func processFile(filename string, detailed bool) {
+ pdqhasher := pdq.NewPDQHasher()
+
+ // Find all image files in the folder
+ path, _ := filepath.Abs(filename)
+ items, err := os.ReadDir(filename)
+ if err != nil {
+ log.Fatal(err)
+ }
+
+ numPDQHash := 0
+ var prevHash *types.Hash256
+
+ for _, item := range items {
+ fullPath := filepath.Join(path, item.Name())
+ if !item.IsDir() {
+ // Check if file is an image
+ filetypeRef, err := filetype.MatchFile(fullPath)
+ if err != nil {
+ log.Fatal(err)
+ }
+ if filetypeRef.MIME.Type == "image" {
+ hashAndQuality := pdqhasher.FromFile(fullPath)
+ delta := 0
+ if numPDQHash == 0 {
+ delta = 0
+ } else {
+ delta = hashAndQuality.Hash.HammingDistance(prevHash)
+ }
+
+ if detailed {
+ log.Printf("hash=%s,norm=%d,delta=%d,quality=%d,filename=%s", hashAndQuality.Hash.String(), hashAndQuality.Hash.HammingNorm(), delta, hashAndQuality.Quality, item.Name())
+ } else {
+ log.Printf("%s,%d,%s", hashAndQuality.Hash.String(), hashAndQuality.Quality, item.Name())
+ }
+
+ prevHash = hashAndQuality.Hash
+ numPDQHash++
+ }
+ }
+ }
+}
+
+func main() {
+ var folder string
+ var detailedOutput bool
+
+ flag.StringVar(&folder, "folder", "", "Folder to scan")
+ flag.BoolVar(&detailedOutput, "detailed", false, "Detailed output")
+
+ flag.Parse()
+
+ // Check if folder exists and is a folder
+ fileInfo, err := os.Stat(folder)
+ if err != nil {
+ log.Fatal(err)
+ }
+ if !fileInfo.IsDir() {
+ log.Fatalf("'%s' is not a folder", folder)
+ }
+
+ vips.LoggingSettings(nil, vips.LogLevelMessage)
+ vips.Startup(&vips.Config{
+ ConcurrencyLevel: 0,
+ MaxCacheFiles: 5,
+ MaxCacheMem: 50 * 1024 * 1024,
+ MaxCacheSize: 100,
+ ReportLeaks: false,
+ CacheTrace: false,
+ CollectStats: false,
+ })
+ defer vips.Shutdown()
+
+ processFile(folder, detailedOutput)
+}
diff --git a/go.mod b/go.mod
@@ -0,0 +1,15 @@
+module github.com/MTRNord/pdqhash-go
+
+go 1.21.7
+
+require (
+ github.com/davidbyttow/govips/v2 v2.13.0
+ github.com/h2non/filetype v1.1.3
+ golang.org/x/exp v0.0.0-20240222234643-814bf88cf225
+)
+
+require (
+ golang.org/x/image v0.15.0 // indirect
+ golang.org/x/net v0.21.0 // indirect
+ golang.org/x/text v0.14.0 // indirect
+)
diff --git a/go.sum b/go.sum
@@ -0,0 +1,55 @@
+github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davidbyttow/govips/v2 v2.13.0 h1:5MK9ZcXZC5GzUR9Ca8fJwOYqMgll/H096ec0PJP59QM=
+github.com/davidbyttow/govips/v2 v2.13.0/go.mod h1:LPTrwWtNa5n4yl9UC52YBOEGdZcY5hDTP4Ms2QWasTw=
+github.com/h2non/filetype v1.1.3 h1:FKkx9QbD7HR/zjK1Ia5XiBsq9zdLi5Kf3zGyFTAFkGg=
+github.com/h2non/filetype v1.1.3/go.mod h1:319b3zT68BvV+WRj7cwy856M2ehB3HqNOt6sy1HndBY=
+github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
+github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
+github.com/niemeyer/pretty v0.0.0-20200227124842-a10e7caefd8e/go.mod h1:zD1mROLANZcx1PVRCS0qkT7pwLkGfwJo4zjcN/Tysno=
+github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
+github.com/stretchr/testify v1.6.1 h1:hDPOHmpOpP40lSULcqw7IrRb/u7w6RpDC9399XyoNd0=
+github.com/stretchr/testify v1.6.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/yuin/goldmark v1.4.13/go.mod h1:6yULJ656Px+3vBD8DxQVa3kxgyrAnzto9xy5taEt/CY=
+golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/crypto v0.0.0-20210921155107-089bfa567519/go.mod h1:GvvjBRRGRdwPK5ydBHafDWAxML/pGHZbMvKqRZ5+Abc=
+golang.org/x/exp v0.0.0-20240222234643-814bf88cf225 h1:LfspQV/FYTatPTr/3HzIcmiUFH7PGP+OQ6mgDYo3yuQ=
+golang.org/x/exp v0.0.0-20240222234643-814bf88cf225/go.mod h1:CxmFvTBINI24O/j8iY7H1xHzx2i4OsyguNBmN/uPtqc=
+golang.org/x/image v0.5.0/go.mod h1:FVC7BI/5Ym8R25iw5OLsgshdUBbT1h5jZTpA+mvAdZ4=
+golang.org/x/image v0.15.0 h1:kOELfmgrmJlw4Cdb7g/QGuB3CvDrXbqEIww/pNtNBm8=
+golang.org/x/image v0.15.0/go.mod h1:HUYqC05R2ZcZ3ejNQsIHQDQiwWM4JBqmm6MKANTp4LE=
+golang.org/x/mod v0.6.0-dev.0.20220419223038-86c51ed26bb4/go.mod h1:jJ57K6gSWd91VN4djpZkiMVwK6gcyfeH4XE8wZrZaV4=
+golang.org/x/net v0.0.0-20190620200207-3b0461eec859/go.mod h1:z5CRVTTTmAJ677TzLLGU+0bjPO0LkuOLi4/5GtJWs/s=
+golang.org/x/net v0.0.0-20210226172049-e18ecbb05110/go.mod h1:m0MpNAwzfU5UDzcl9v0D8zg8gWTRqZa9RBIspLL5mdg=
+golang.org/x/net v0.0.0-20220722155237-a158d28d115b/go.mod h1:XRhObCWvk6IyKnWLug+ECip1KBveYUHfp+8e9klMJ9c=
+golang.org/x/net v0.7.0/go.mod h1:2Tu9+aMcznHK/AK1HMvgo6xiTLG5rD5rZLDS+rp2Bjs=
+golang.org/x/net v0.21.0 h1:AQyQV4dYCvJ7vGmJyKki9+PBdyvhkSd8EIx/qb0AYv4=
+golang.org/x/net v0.21.0/go.mod h1:bIjVDfnllIU7BJ2DNgfnXvpSvtn8VRwhlsaeUTyUS44=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20220722155255-886fb9371eb4/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
+golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20220520151302-bc2c85ada10a/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20220722155257-8c9f86f7a55f/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.5.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
+golang.org/x/term v0.0.0-20210927222741-03fcf44c2211/go.mod h1:jbD1KX2456YbFQfuXm/mYQcufACuNUgVhRMnK/tPxf8=
+golang.org/x/term v0.5.0/go.mod h1:jMB1sMXY+tzblOD4FWmEbocvup2/aLOaQEp7JmGp78k=
+golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+golang.org/x/text v0.3.3/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
+golang.org/x/text v0.3.7/go.mod h1:u+2+/6zg+i71rQMx5EYifcz6MCKuco9NR6JIITiCfzQ=
+golang.org/x/text v0.7.0/go.mod h1:mrYo+phRRbMaCq/xk9113O4dZlRixOauAjOtrjsXDZ8=
+golang.org/x/text v0.14.0 h1:ScX5w1eTa3QqT8oi6+ziP7dTV1S2+ALU0bI+0zXKWiQ=
+golang.org/x/text v0.14.0/go.mod h1:18ZOQIKpY8NJVqYksKHtTdi31H5itFRjB5/qKTNYzSU=
+golang.org/x/tools v0.0.0-20180917221912-90fa682c2a6e/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
+golang.org/x/tools v0.0.0-20191119224855-298f0cb1881e/go.mod h1:b+2E5dAYhXwXZwtnZ6UAqBI28+e2cm9otk0dWdXHAEo=
+golang.org/x/tools v0.1.12/go.mod h1:hNGJHUnrk76NpqgfD5Aqm5Crs+Hm0VOH/i9J2+nxYbc=
+golang.org/x/xerrors v0.0.0-20190717185122-a985d3407aa7/go.mod h1:I/5z698sn9Ka8TeJc9MKroUUfqBBauWjQqLJ2OPfmY0=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/check.v1 v1.0.0-20200902074654-038fdea0a05b/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c h1:dUUwHk2QECo/6vqA44rthZ8ie2QXMNeKRTHCNY2nXvo=
+gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/helpers/helpers.go b/helpers/helpers.go
@@ -0,0 +1,79 @@
+package helpers
+
+import "golang.org/x/exp/constraints"
+
+func Abs[T constraints.Integer](x T) T {
+ if x < 0 {
+ return -x
+ }
+ return x
+}
+
+func Torben(m [][]float64, numRows, numCols int) float64 {
+ n := numRows * numCols
+ midn := (n + 1) / 2
+ less := 0
+ greater := 0
+ equal := 0
+ min := m[0][0]
+ max := m[0][0]
+ guess := 0.0
+ maxltguess := 0.0
+ mingtguess := 0.0
+ for i := 0; i < numRows; i++ {
+ for j := 0; j < numCols; j++ {
+ v := m[i][j]
+ if v < min {
+ min = v
+ }
+
+ if v > max {
+ max = v
+ }
+ }
+ }
+
+ for {
+ guess = (min + max) / 2
+ less = 0
+ greater = 0
+ equal = 0
+ maxltguess = min
+ mingtguess = max
+
+ for i := 0; i < numRows; i++ {
+ for j := 0; j < numCols; j++ {
+ v := m[i][j]
+ if v < guess {
+ less++
+ if v > maxltguess {
+ maxltguess = v
+ }
+ } else if v > guess {
+ greater++
+ if v < mingtguess {
+ mingtguess = v
+ }
+ } else {
+ equal++
+ }
+ }
+ }
+
+ if less <= midn && greater <= midn {
+ break
+ } else if less > greater {
+ max = maxltguess
+ } else {
+ min = mingtguess
+ }
+ }
+
+ if less >= midn {
+ return maxltguess
+ } else if less+equal >= midn {
+ return guess
+ } else {
+ return mingtguess
+ }
+}
diff --git a/pdq_hasher.go b/pdq_hasher.go
@@ -0,0 +1,549 @@
+package pdq
+
+import (
+ "log"
+ "math"
+
+ "github.com/MTRNord/pdqhash-go/helpers"
+ "github.com/MTRNord/pdqhash-go/types"
+ "github.com/davidbyttow/govips/v2/vips"
+
+ _ "image/jpeg"
+ _ "image/png"
+)
+
+// From Wikipedia: standard RGB to luminance (the 'Y' in 'YUV').
+const LUMA_FROM_R_COEFF = 0.299
+const LUMA_FROM_G_COEFF = 0.587
+const LUMA_FROM_B_COEFF = 0.114
+
+func DCT_MATRIX_SCALE_FACTOR() float64 {
+ return math.Sqrt(2.0 / 64.0)
+}
+
+// Wojciech Jarosz 'Fast Image Convolutions' ACM SIGGRAPH 2001:
+// X,Y,X,Y passes of 1-D box filters produces a 2D tent filter.
+const PDQ_NUM_JAROSZ_XY_PASSES = 2
+
+/*
+Since PDQ uses 64x64 blocks, 1/64th of the image height/width
+respectively is a full block. But since we use two passes, we want half
+that window size per pass. Example: 1024x1024 full-resolution input. PDQ
+downsamples to 64x64. Each 16x16 block of the input produces a single
+downsample pixel. X,Y passes with window size 8 (= 1024/128) average
+pixels with 8x8 neighbors. The second X,Y pair of 1D box-filter passes
+accumulate data from all 16x16.
+*/
+const PDQ_JAROSZ_WINDOW_SIZE_DIVISOR = 128
+
+// Flags for which dihedral-transforms are desired to be produced.
+const PDQ_DO_DIH_ORIGINAL = 0x01
+const PDQ_DO_DIH_ROTATE_90 = 0x02
+const PDQ_DO_DIH_ROTATE_180 = 0x04
+const PDQ_DO_DIH_ROTATE_270 = 0x08
+const PDQ_DO_DIH_FLIPX = 0x10
+const PDQ_DO_DIH_FLIPY = 0x20
+const PDQ_DO_DIH_FLIP_PLUS1 = 0x40
+const PDQ_DO_DIH_FLIP_MINUS1 = 0x80
+const PDQ_DO_DIH_ALL = 0xFF
+
+/**
+ * The only class state is the DCT matrix, so this class may either be
+ * instantiated once per image, or instantiated once and used for all images;
+ * the latter will be slightly faster as the DCT matrix will not need to be
+ * recomputed once per image.
+ */
+type PDQHasher struct {
+ DCT_matrix [][]float64
+}
+
+/**
+ * Container for multiple-value object: the hash is a 64-character hex
+ * string and the quality is an integer in the range 0..100.
+ */
+type HashAndQuality struct {
+ Hash *types.Hash256
+ Quality int
+}
+
+type HashesAndQuality struct {
+ hash *types.Hash256
+ hashRotate90 *types.Hash256
+ hashRotate180 *types.Hash256
+ hashRotate270 *types.Hash256
+ hashFlipX *types.Hash256
+ hashFlipY *types.Hash256
+ hashFlipPlus1 *types.Hash256
+ hashFlipMinus1 *types.Hash256
+ quality int
+}
+
+func NewPDQHasher() *PDQHasher {
+ return &PDQHasher{
+ DCT_matrix: ComputeDCTMatrix(),
+ }
+}
+
+func ComputeDCTMatrix() [][]float64 {
+ d := make([][]float64, 16)
+ for i := 0; i < 16; i++ {
+ di := make([]float64, 64)
+ for j := 0; j < 64; j++ {
+ di[j] = DCT_MATRIX_SCALE_FACTOR() * math.Cos((math.Pi/2.0/64.0)*(float64(i)+1.0)*(2.0*float64(j)+1.0))
+ }
+ d[i] = di
+ }
+
+ return d
+}
+
+func allocateMatrix(numRows, numCols int) [][]float64 {
+ // Create a slice of slices to represent the matrix
+ matrix := make([][]float64, numRows)
+
+ // Allocate memory for each row
+ for i := range matrix {
+ matrix[i] = make([]float64, numCols)
+ }
+
+ return matrix
+}
+
+func (p *PDQHasher) FromFile(filename string) HashAndQuality {
+ params := vips.NewImportParams()
+ params.AutoRotate.Set(false)
+
+ image, err := vips.LoadImageFromFile(filename, params)
+ if err != nil {
+ log.Fatalf("Error opening file: %v", err)
+ }
+
+ // resizing the image proportionally to max 512px width and max 512px height
+ err = image.Thumbnail(512, 512, vips.InterestingNone)
+ if err != nil {
+ log.Fatalf("Error resizing image: %v", err)
+ }
+ numCols := image.Width()
+ numRows := image.Height()
+
+ buffer1 := make([]float64, numCols*numRows)
+ buffer2 := make([]float64, numCols*numRows)
+ buffer64x64 := allocateMatrix(64, 64)
+ buffer16x64 := allocateMatrix(16, 64)
+ buffer16x16 := allocateMatrix(16, 16)
+
+ return p.FromImage(image, buffer1, buffer2, buffer64x64, buffer16x64, buffer16x16)
+}
+
+func (p *PDQHasher) FromImage(image *vips.ImageRef, buffer1, buffer2 []float64, buffer64x64, buffer16x64, buffer16x16 [][]float64) HashAndQuality {
+ numCols := image.Width()
+ numRows := image.Height()
+
+ p.fillFloatLumaFromBufferImage(image, &buffer1)
+
+ return p.pdqHash256FromFloatLuma(buffer1, buffer2, numRows, numCols, buffer64x64, buffer16x64, buffer16x16)
+}
+
+func (p *PDQHasher) fillFloatLumaFromBufferImage(image *vips.ImageRef, luma *[]float64) {
+ numCols := image.Width()
+ numRows := image.Height()
+
+ err := image.ToColorSpace(vips.InterpretationSRGB)
+ if err != nil {
+ log.Fatalf("Error converting to RGB: %v", err)
+ }
+ goImage, err := image.ToImage(nil)
+ if err != nil {
+ log.Fatalf("Error converting to Go image: %v", err)
+ }
+
+ for i := 0; i < numRows; i++ {
+ for j := 0; j < numCols; j++ {
+ colorArray := goImage.At(j, i)
+ r, g, b, _ := colorArray.RGBA()
+ (*luma)[i*numCols+j] = LUMA_FROM_R_COEFF*float64(r) + LUMA_FROM_G_COEFF*float64(g) + LUMA_FROM_B_COEFF*float64(b)
+ }
+ }
+}
+
+func (p *PDQHasher) pdqHash256FromFloatLuma(fullBuffer1, fullBuffer2 []float64, numRows, numCols int, buffer64x64, buffer16x64, buffer16x16 [][]float64) HashAndQuality {
+ windowSizeAlongRows := p.computeJaroszWindowSize(numCols)
+ windowSizeAlongCols := p.computeJaroszWindowSize(numRows)
+ p.jaroszFilterFloat(&fullBuffer1, &fullBuffer2, numRows, numCols, windowSizeAlongRows, windowSizeAlongCols, PDQ_NUM_JAROSZ_XY_PASSES)
+
+ p.decimateFloat(&fullBuffer1, numRows, numCols, &buffer64x64)
+ quality := p.computePDQImageDomainQualityMetric(buffer64x64)
+ p.dct64To16(&buffer64x64, &buffer16x64, &buffer16x16)
+ hash := p.pdqBuffer16x16ToBits(buffer16x16)
+
+ return HashAndQuality{hash, quality}
+}
+
+func (p *PDQHasher) dihedralFromFile(filename string, dihedralFlags int) HashesAndQuality {
+ vips.Startup(nil)
+ defer vips.Shutdown()
+ image, err := vips.NewImageFromFile(filename)
+ if err != nil {
+ log.Fatalf("Error opening file: %v", err)
+ }
+
+ numRows := image.Height()
+ numCols := image.Width()
+
+ buffer1 := make([]float64, numCols*numRows)
+ buffer2 := make([]float64, numCols*numRows)
+
+ buffer64x64 := allocateMatrix(64, 64)
+ buffer16x64 := allocateMatrix(16, 64)
+ buffer16x16 := allocateMatrix(16, 16)
+ buffer16x16Aux := allocateMatrix(16, 16)
+
+ return p.dihedralFromBufferedImage(image, buffer1, buffer2, buffer64x64, buffer16x64, buffer16x16, buffer16x16Aux, dihedralFlags)
+}
+
+func (p *PDQHasher) dihedralFromBufferedImage(image *vips.ImageRef, buffer1, buffer2 []float64, buffer64x64, buffer16x64, buffer16x16, buffer16x16Aux [][]float64, dihedralFlags int) HashesAndQuality {
+ numRows := image.Height()
+ numCols := image.Width()
+
+ p.fillFloatLumaFromBufferImage(image, &buffer1)
+
+ return p.pdqHash256esFromFloatLuma(buffer1, buffer2, numRows, numCols, buffer64x64, buffer16x64, buffer16x16, buffer16x16Aux, dihedralFlags)
+}
+
+func (p *PDQHasher) pdqHash256esFromFloatLuma(fullBuffer1, fullBuffer2 []float64, numRows, numCols int, buffer64x64, buffer16x64, buffer16x16, buffer16x16Aux [][]float64, dihedralFlags int) HashesAndQuality {
+ windowSizeAlongRows := p.computeJaroszWindowSize(numCols)
+ windowSizeAlongCols := p.computeJaroszWindowSize(numRows)
+ p.jaroszFilterFloat(&fullBuffer1, &fullBuffer2, numRows, numCols, windowSizeAlongRows, windowSizeAlongCols, PDQ_NUM_JAROSZ_XY_PASSES)
+
+ p.decimateFloat(&fullBuffer1, numRows, numCols, &buffer64x64)
+ quality := p.computePDQImageDomainQualityMetric(buffer64x64)
+ p.dct64To16(&buffer64x64, &buffer16x64, &buffer16x16)
+
+ var hash *types.Hash256
+ var hashRotate90 *types.Hash256
+ var hashRotate180 *types.Hash256
+ var hashRotate270 *types.Hash256
+ var hashFlipX *types.Hash256
+ var hashFlipY *types.Hash256
+ var hashFlipPlus1 *types.Hash256
+ var hashFlipMinus1 *types.Hash256
+
+ if dihedralFlags&PDQ_DO_DIH_ORIGINAL != 0 {
+ hash = p.pdqBuffer16x16ToBits(buffer16x16)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_ROTATE_90 != 0 {
+ p.dct16OriginalToRotate90(&buffer16x16, &buffer16x16Aux)
+ hashRotate90 = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_ROTATE_180 != 0 {
+ p.dct16OriginalToRotate180(&buffer16x16, &buffer16x16Aux)
+ hashRotate180 = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_ROTATE_270 != 0 {
+ p.dct16OriginalToRotate270(&buffer16x16, &buffer16x16Aux)
+ hashRotate270 = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_FLIPX != 0 {
+ p.dct16OriginalToFlipX(&buffer16x16, &buffer16x16Aux)
+ hashFlipX = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_FLIPY != 0 {
+ p.dct16OriginalToFlipY(&buffer16x16, &buffer16x16Aux)
+ hashFlipY = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_FLIP_PLUS1 != 0 {
+ p.dct16OriginalToFlipPlus1(&buffer16x16, &buffer16x16Aux)
+ hashFlipPlus1 = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ if dihedralFlags&PDQ_DO_DIH_FLIP_MINUS1 != 0 {
+ p.dct16OriginalToFlipMinus1(&buffer16x16, &buffer16x16Aux)
+ hashFlipMinus1 = p.pdqBuffer16x16ToBits(buffer16x16Aux)
+ }
+
+ return HashesAndQuality{hash, hashRotate90, hashRotate180, hashRotate270, hashFlipX, hashFlipY, hashFlipPlus1, hashFlipMinus1, quality}
+}
+
+// numRows x numCols in row-major order
+func (p *PDQHasher) decimateFloat(in *[]float64, inNumRows, inNumCols int, out *[][]float64) {
+ for i := 0; i < 64; i++ {
+ ini := int(((float64(i) + 0.5) * float64(inNumRows)) / 64)
+ for j := 0; j < 64; j++ {
+ inj := int(((float64(j) + 0.5) * float64(inNumCols)) / 64)
+ (*out)[i][j] = (*in)[ini*inNumCols+inj]
+ }
+ }
+}
+
+/**
+ * This is all heuristic (see the PDQ hashing doc). Quantization
+ * matters since we want to count *significant* gradients, not just the
+ * some of many small ones. The constants are all manually selected, and
+ * tuned as described in the document.
+ */
+func (p *PDQHasher) computePDQImageDomainQualityMetric(buffer64x64 [][]float64) int {
+ gradientSum := 0
+ for i := 0; i < 63; i++ {
+ for j := 0; j < 64; j++ {
+ u := buffer64x64[i][j]
+ v := buffer64x64[i+1][j]
+ d := int(((u - v) * 100) / 255)
+ gradientSum += int(helpers.Abs(d))
+ }
+ }
+ for i := 0; i < 64; i++ {
+ for j := 0; j < 63; j++ {
+ u := buffer64x64[i][j]
+ v := buffer64x64[i][j+1]
+ d := int(((u - v) * 100) / 255)
+ gradientSum += int(helpers.Abs(d))
+ }
+ }
+ quality := int(gradientSum / 90)
+ if quality > 100 {
+ quality = 100
+ }
+ return quality
+}
+
+/**
+ * Full 64x64 to 64x64 can be optimized e.g. the Lee algorithm.
+ * But here we only want slots (1-16)x(1-16) of the full 64x64 output.
+ * Careful experiments showed that using Lee along all 64 slots in one
+ * dimension, then Lee along 16 slots in the second, followed by
+ * extracting slots 1-16 of the output, was actually slower than the
+ * current implementation which is completely non-clever/non-Lee but
+ * computes only what is needed.
+ */
+func (p *PDQHasher) dct64To16(A, T, B *([][]float64)) {
+ D := p.DCT_matrix
+
+ *T = make([][]float64, 16)
+ for i := 0; i < 16; i++ {
+ ti := make([]float64, 64)
+
+ for j := 0; j < 64; j++ {
+ tij := 0.0
+ for k := 0; k < 64; k++ {
+ tij += D[i][k] * (*A)[k][j]
+ }
+ ti[j] = tij
+ }
+ (*T)[i] = ti
+ }
+
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ sumk := 0.0
+ for k := 0; k < 64; k++ {
+ sumk += (*T)[i][k] * D[j][k]
+ }
+ (*B)[i][j] = sumk
+ }
+ }
+}
+
+/*
+ -------------------------------------
+ orig rot90 rot180 rot270
+ noxpose xpose noxpose xpose
+ + + + + - + - + + - + - - - - -
+ + + + + - + - + - + - + + + + +
+ + + + + - + - + + - + - - - - -
+ + + + + - + - + - + - + + + + +
+
+ flipx flipy flipplus flipminus
+ noxpose noxpose xpose xpose
+ - - - - - + - + + + + + + - + -
+ + + + + - + - + + + + + - + - +
+ - - - - - + - + + + + + + - + -
+ + + + + - + - + + + + + - + - +
+ -------------------------------------
+*/
+
+func (p *PDQHasher) dct16OriginalToRotate90(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if (j & 1) != 0 {
+ (*B)[j][i] = (*A)[i][j]
+ } else {
+ (*B)[j][i] = -(*A)[i][j]
+ }
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToRotate180(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if ((i + j) & 1) != 0 {
+ (*B)[i][j] = -(*A)[i][j]
+ } else {
+ (*B)[i][j] = (*A)[i][j]
+ }
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToRotate270(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if (i & 1) != 0 {
+ (*B)[j][i] = (*A)[i][j]
+ } else {
+ (*B)[j][i] = -(*A)[i][j]
+ }
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToFlipX(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if (i & 1) != 0 {
+ (*B)[i][j] = (*A)[i][j]
+ } else {
+ (*B)[i][j] = -(*A)[i][j]
+ }
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToFlipY(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if (j & 1) != 0 {
+ (*B)[i][j] = (*A)[i][j]
+ } else {
+ (*B)[i][j] = -(*A)[i][j]
+ }
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToFlipPlus1(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ (*B)[i][j] = (*A)[i][j]
+ }
+ }
+}
+
+func (p *PDQHasher) dct16OriginalToFlipMinus1(A, B *[][]float64) {
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if ((i + j) & 1) != 0 {
+ (*B)[j][i] = -(*A)[i][j]
+ } else {
+ (*B)[j][i] = (*A)[i][j]
+ }
+ }
+ }
+}
+
+/**
+ * Each bit of the 16x16 output hash is for whether the given frequency
+ * component is greater than the median frequency component or not.
+ */
+func (p *PDQHasher) pdqBuffer16x16ToBits(dctOutput16x16 [][]float64) *types.Hash256 {
+ hash := types.Hash256{}
+ dctMedian := helpers.Torben(dctOutput16x16, 16, 16)
+ for i := 0; i < 16; i++ {
+ for j := 0; j < 16; j++ {
+ if dctOutput16x16[i][j] > dctMedian {
+ hash.SetBit(i*16 + j)
+ }
+ }
+ }
+ return &hash
+}
+
+// Round up.
+func (p *PDQHasher) computeJaroszWindowSize(dimension int) int {
+ return (dimension + PDQ_JAROSZ_WINDOW_SIZE_DIVISOR - 1) / PDQ_JAROSZ_WINDOW_SIZE_DIVISOR
+}
+
+func (p *PDQHasher) jaroszFilterFloat(buffer1, buffer2 *[]float64, numRows, numCols, windowSizeAlongRows, windowSizeAlongCols, nreps int) {
+ for i := 0; i < nreps; i++ {
+ p.boxAlongRowsFloat(buffer1, buffer2, numRows, numCols, windowSizeAlongRows)
+ p.boxAlongColsFloat(buffer2, buffer1, numRows, numCols, windowSizeAlongCols)
+ }
+}
+
+func (p *PDQHasher) box1DFloat(invec *[]float64, inStartOffset int, outvec *[]float64, outStartOffset, vectorLength, stride, fullWindowSize int) {
+ halfWindowSize := int((fullWindowSize + 2) / 2)
+ phase_1_nreps := int(halfWindowSize - 1)
+ phase_2_nreps := int(fullWindowSize - halfWindowSize + 1)
+ phase_3_nreps := int(vectorLength - fullWindowSize)
+ phase_4_nreps := int(halfWindowSize - 1)
+ li := 0 // Index of left edge of read window, for subtracts
+ ri := 0 // Index of right edge of read windows, for adds
+ oi := 0 // Index of output vector
+ sum := 0.0
+ currentWindowSize := 0
+
+ // PHASE 1: ACCUMULATE FIRST SUM NO WRITES
+ i := 0
+ for i < phase_1_nreps {
+ sum += (*invec)[inStartOffset+ri]
+ currentWindowSize += 1
+ ri += stride
+ i += 1
+ }
+
+ // PHASE 2: INITIAL WRITES WITH SMALL WINDOW
+ i = 0
+ for i < phase_2_nreps {
+ sum += (*invec)[inStartOffset+ri]
+ currentWindowSize += 1
+ (*outvec)[outStartOffset+oi] = sum / float64(currentWindowSize)
+ ri += stride
+ oi += stride
+ i += 1
+ }
+
+ // PHASE 3: WRITES WITH FULL WINDOW
+ i = 0
+ for i < phase_3_nreps {
+ sum += (*invec)[inStartOffset+ri]
+ sum -= (*invec)[inStartOffset+li]
+ (*outvec)[outStartOffset+oi] = sum / float64(currentWindowSize)
+ li += stride
+ ri += stride
+ oi += stride
+ i += 1
+ }
+
+ // PHASE 4: FINAL WRITES WITH SMALL WINDOW
+ i = 0
+ for i < phase_4_nreps {
+ sum -= (*invec)[inStartOffset+li]
+ currentWindowSize -= 1
+ (*outvec)[outStartOffset+oi] = sum / float64(currentWindowSize)
+ li += stride
+ oi += stride
+ i += 1
+ }
+}
+
+/**
+ * input - matrix as numRows x numCols in row-major order
+ * output - matrix as numRows x numCols in row-major order
+ */
+func (p *PDQHasher) boxAlongRowsFloat(input, output *[]float64, numRows, numCols, windowSize int) {
+ for i := 0; i < numRows; i++ {
+ p.box1DFloat(input, i*numCols, output, i*numCols, numCols, 1, windowSize)
+ }
+}
+
+func (p *PDQHasher) boxAlongColsFloat(input, output *[]float64, numRows, numCols, windowSize int) {
+ for i := 0; i < numCols; i++ {
+ p.box1DFloat(input, i, output, i, numRows, numCols, windowSize)
+ }
+}
diff --git a/types/hash256.go b/types/hash256.go
@@ -0,0 +1,237 @@
+package types
+
+import (
+ "fmt"
+ "strconv"
+ "strings"
+)
+
+// 16 slots of 16 bytes each
+// See hashing/pdq/README-MIH.md in upstream repo for why not 8x32 or 32x8, etc.
+const HASH256_NUM_SLOTS = 16
+const HASH256_HEX_NUM_NYBBLES = 4 * HASH256_NUM_SLOTS
+
+type Hash256 struct {
+ W [HASH256_NUM_SLOTS]int
+}
+
+func (h *Hash256) GetNumWords() int {
+ return HASH256_NUM_SLOTS
+}
+
+func (h *Hash256) Clone() Hash256 {
+ rv := Hash256{}
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ rv.W[i] = h.W[i]
+ }
+ return rv
+}
+
+func (h *Hash256) String() string {
+ i := HASH256_NUM_SLOTS - 1
+ var result []string
+
+ for i >= 0 {
+ result = append(result, fmt.Sprintf("%04x", h.W[i]&0xFFFF))
+ i = i - 1
+ }
+
+ return strings.Join(result, "")
+}
+
+func (h *Hash256) ToHexString() string {
+ return h.String()
+}
+
+func Hash256FromHexString(s string) (*Hash256, error) {
+ if len(s) != HASH256_HEX_NUM_NYBBLES {
+ return nil, fmt.Errorf("invalid format: %s", s)
+ }
+
+ rv := &Hash256{}
+ i := HASH256_NUM_SLOTS
+ for x := 0; x < len(s); x += 4 {
+ i -= 1
+ val, err := strconv.ParseUint(s[x:x+4], 16, 16)
+ if err != nil {
+ return nil, fmt.Errorf("incorrect format: %s", s)
+ }
+ rv.W[i] = int(val)
+ }
+ return rv, nil
+}
+
+func (h *Hash256) HammingNorm16(h2 int) int {
+ return h.BitCount(h2 & 0xFFFF)
+}
+
+func (h *Hash256) BitCount(x int) int {
+ x -= (x >> 1) & 0x55555555
+ x = ((x >> 2) & 0x33333333) + (x & 0x33333333)
+ x = ((x >> 4) + x) & 0x0F0F0F0F
+ x += x >> 8
+ x += x >> 16
+ return x & 0x0000003F
+}
+
+func (h *Hash256) ClearAll() {
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ h.W[i] = 0
+ }
+}
+
+func (h *Hash256) SetAll() {
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ h.W[i] = 0xFFFF
+ }
+}
+
+func (h *Hash256) HammingNorm() int {
+ n := 0
+ i := 0
+ for i < HASH256_NUM_SLOTS {
+ n += h.HammingNorm16(h.W[i])
+ i += 1
+ }
+ return n
+}
+
+func (h *Hash256) HammingDistance(that *Hash256) int {
+ n := 0
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ n += h.HammingNorm16(h.W[i] ^ that.W[i])
+ }
+ return n
+}
+
+func (h *Hash256) HammingDistanceLE(that *Hash256, d int) bool {
+ e := 0
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ e += h.HammingNorm16(h.W[i] ^ that.W[i])
+ if e > d {
+ return false
+ }
+ }
+ return true
+}
+
+func (h *Hash256) SetBit(k int) {
+ h.W[(k&255)>>4] |= 1 << (k & 15)
+}
+
+func (h *Hash256) FlipBit(k int) {
+ h.W[(k&255)>>4] ^= 1 << (k & 15)
+}
+
+func (h *Hash256) BitwiseXOR(that *Hash256) Hash256 {
+ rv := Hash256{}
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ rv.W[i] = (h.W[i] ^ that.W[i])
+ }
+ return rv
+}
+
+func (h *Hash256) BitwiseAND(that *Hash256) Hash256 {
+ rv := Hash256{}
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ rv.W[i] = (h.W[i] & that.W[i])
+ }
+ return rv
+}
+
+func (h *Hash256) BitwiseOR(that *Hash256) Hash256 {
+ rv := Hash256{}
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ rv.W[i] = (h.W[i] | that.W[i])
+ }
+ return rv
+}
+
+func (h *Hash256) BitwiseNOT() Hash256 {
+ rv := Hash256{}
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ rv.W[i] = ((^h.W[i]) & 0xFFFF)
+ }
+ return rv
+}
+
+func (h *Hash256) DumpBits() string {
+ var str []string
+
+ i := HASH256_NUM_SLOTS - 1
+ for i >= 0 {
+ word := h.W[i] & 0xFFFF
+ var bits []string
+ for j := 15; j >= 0; j-- {
+ if (word & (1 << uint(j))) != 0 {
+ bits = append(bits, "1")
+ } else {
+ bits = append(bits, "0")
+ }
+ }
+ str = append(str, strings.Join(bits, " "))
+ i--
+ }
+ return strings.Join(str, "\n")
+}
+
+func (h *Hash256) DumpBitsAcross() string {
+ var str []string
+
+ i := HASH256_NUM_SLOTS - 1
+ for i >= 0 {
+ word := h.W[i] & 0xFFFF
+ for j := 15; j >= 0; j-- {
+ if (word & (1 << uint(j))) != 0 {
+ str = append(str, "1")
+ } else {
+ str = append(str, "0")
+ }
+ }
+ i--
+ }
+ return strings.Join(str, " ")
+}
+
+func (h *Hash256) DumpWords() string {
+ var words []string
+
+ // Iterate over the reversed list of words
+ for i := len(h.W) - 1; i >= 0; i-- {
+ words = append(words, strconv.Itoa(int(h.W[i])))
+ }
+
+ // Join the words with commas
+ return strings.Join(words, ",")
+}
+
+func (h *Hash256) Eq(other *Hash256) bool {
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ if h.W[i] != other.W[i] {
+ return false
+ }
+ }
+ return true
+}
+
+func (h *Hash256) Greater(other *Hash256) bool {
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ if h.W[i] > other.W[i] {
+ return true
+ } else if h.W[i] < other.W[i] {
+ return false
+ }
+ }
+ return false
+}
+
+func (h *Hash256) Less(other *Hash256) bool {
+ for i := 0; i < HASH256_NUM_SLOTS; i++ {
+ if h.W[i] < other.W[i] {
+ return true
+ } else if h.W[i] > other.W[i] {
+ return false
+ }
+ }
+ return false
+}
