Project

General

Profile

« Previous | Next » 

Revision f079bf77

Added by Leszek Koltunski about 1 year ago

PruningTables now support numBits=20,24.
Progress with TablebasesPruning.

View differences:

src/main/java/org/distorted/objectlib/tablebases/PruningTable.java
13 13

  
14 14
class PruningTable
15 15
{
16
  private static final int HEADER_SIZE = 5;
16
  static final int[] SUPPORTED = {4,8,12,16,20,24};
17

  
18
  private static final int HEADER_SIZE = 6;
17 19
  private byte[] mData;
18 20
  private int mNumBits;
19 21
  private int mBucketBytes;
......
49 51
    mData[0] = (byte)mLevel;
50 52
    mData[1] = (byte)mBucketBytes;
51 53
    mData[2] = (byte)mNumBits;
52
    mData[3] = (byte)(mNumBuckets/256);
53
    mData[4] = (byte)(mNumBuckets%256);
54
    mData[3] = (byte)(mNumBuckets>>>16);
55
    mData[4] = (byte)(mNumBuckets>>> 8);
56
    mData[5] = (byte)(mNumBuckets&0xff);
54 57
    }
55 58

  
56 59
///////////////////////////////////////////////////////////////////////////////////////////////////
......
102 105
               break;
103 106
      case  8: ret = (mData[bytes]&0xff);
104 107
               break;
105
      case 12: ret = (bits%8)!=0 ? ((mData[bytes]&0xf)*256 + (mData[bytes+1]&0xff)) : ( (mData[bytes]&0xff)*16 + ((mData[bytes+1]>>>4)&0xf));
108
      case 12: ret = (bits%8)!=0 ? (((mData[bytes]&0xf)<<8) + (mData[bytes+1]&0xff)) : (((mData[bytes]&0xff)<<4) + ((mData[bytes+1]>>>4)&0xf));
109
               break;
110
      case 16: ret = ((mData[bytes]&0xff)<<8) + (mData[bytes+1]&0xff);
111
               break;
112
      case 20: if( (bits%8) !=0 ) ret = (((mData[bytes]&0x0f)<<16) + ((mData[bytes+1]&0xff)<<8) + ( mData[bytes+2]     &0xff));
113
               else               ret = (((mData[bytes]&0xff)<<12) + ((mData[bytes+1]&0xff)<<4) + ((mData[bytes+2]>>>4)&0x0f));
106 114
               break;
107
      case 16: ret = (mData[bytes]&0xff)*256 + (mData[bytes+1]&0xff);
115
      case 24: ret = ((mData[bytes]&0xff)<<16) + ((mData[bytes+1]&0xff)<<8) + (mData[bytes+2]&0xff);
108 116
               break;
109 117
      }
110 118

  
......
133 141
               else
134 142
                 {
135 143
                 mData[bytes]  = (byte)(value>>>4);
136
                 mData[bytes+1]= (byte)((byte)(value<<4) + (mData[bytes+1]&( 0xf)));
144
                 mData[bytes+1]= (byte)((byte)(value<<4) + (mData[bytes+1]&0xf));
137 145
                 }
138 146
               break;
139 147
      case 16: mData[bytes]   = (byte)(value>>>8);
140 148
               mData[bytes+1] = (byte)(value&(0xff));
149
               break;
150
      case 20: if( (bits%8) !=0 )
151
                 {
152
                 mData[bytes]  = (byte)((mData[bytes]&(~0xf)) + (value>>>16));
153
                 mData[bytes+1]= (byte)(value>>>8);
154
                 mData[bytes+2]= (byte)(value&(0xff));
155
                 }
156
               else
157
                 {
158
                 mData[bytes]  = (byte)(value>>>12);
159
                 mData[bytes+1]= (byte)(value>>>4);
160
                 mData[bytes+2]= (byte)((byte)(value<<4) + (mData[bytes+2]&0xf));
161
                 }
162
               break;
163
      case 24: mData[bytes]   = (byte)(value>>>16);
164
               mData[bytes+1] = (byte)(value>>>8);
165
               mData[bytes+2] = (byte)(value&(0xff));
166
               break;
141 167
      }
142 168
    }
143 169

  
......
240 266
///////////////////////////////////////////////////////////////////////////////////////////////////
241 267
// PUBLIC API
242 268
///////////////////////////////////////////////////////////////////////////////////////////////////
243
// only numBits = 4,8,12,16 actually supported
269
// only numBits = 4,8,12,16,20,24 actually supported
244 270

  
245 271
  PruningTable(Tablebase table, int level, int numBits)
246 272
    {
......
251 277

  
252 278
  PruningTable(Tablebase table, int level)
253 279
    {
254
    int[] supported = {4,8,12,16};
255 280
    int minimum = 0, chosen =  0;
256 281
    int size = retNumPositions(table,level);
257 282
    int tableSize = table.getSize();
258 283

  
259 284
    android.util.Log.e("D", "----- PRUNING TABLE LEVEL "+level+" ------");
260 285

  
261
    for(int i=0; i<supported.length; i++)
286
    for(int i=0; i<SUPPORTED.length; i++)
262 287
      {
263
      int approx = computeApproximateSize( tableSize, size, supported[i]);
288
      int approx = computeApproximateSize( tableSize, size, SUPPORTED[i]);
264 289

  
265 290
      if( i==0 || approx<minimum )
266 291
        {
......
268 293
        chosen  = i;
269 294
        }
270 295

  
271
      android.util.Log.e("D", "trying numBits: "+supported[i]+" approx size: "+approx);
296
      android.util.Log.e("D", "trying numBits: "+SUPPORTED[i]+" approx size: "+approx);
272 297
      }
273 298

  
274
    construct(table,level,supported[chosen]);
299
    construct(table,level,SUPPORTED[chosen]);
275 300
    }
276 301

  
277 302
///////////////////////////////////////////////////////////////////////////////////////////////////
......
283 308
    mLevel       = ((int)mData[0])&0xff;
284 309
    mBucketBytes = ((int)mData[1])&0xff;
285 310
    mNumBits     = ((int)mData[2])&0xff;
286
    mNumBuckets  =(((int)mData[3])&0xff)*256 + ((int)mData[4])&0xff;
311
    mNumBuckets  =((((int)mData[3])&0xff)<<16) + ((((int)mData[4])&0xff)<<8) + ((int)mData[5])&0xff;
287 312
    }
288 313

  
289 314
///////////////////////////////////////////////////////////////////////////////////////////////////
src/main/java/org/distorted/objectlib/tablebases/TablebasesAbstract.java
548 548

  
549 549
    public void testPruning(int level)
550 550
      {
551
      PruningTable table = new PruningTable(mTablebase,level);
552
      int size = mTablebase.getSize();
551
      for( int supp : PruningTable.SUPPORTED )
552
        {
553
        PruningTable table = new PruningTable(mTablebase, level, supp);
554
        int size = mTablebase.getSize();
553 555

  
554
      StringBuilder sb = new StringBuilder();
555
      int num=0;
556
        StringBuilder sb = new StringBuilder();
557
        int num = 0;
556 558

  
557
      for(int i=0; i<size; i++)
558
        {
559
        if( table.belongs(i) )
559
        for(int i=0; i<size; i++)
560 560
          {
561
          if( (num%10)==0 ) sb.append("\n");
562
          num++;
563
          sb.append(i);
564
          sb.append(' ');
561
          if (table.belongs(i))
562
            {
563
            if ((num % 10) == 0) sb.append("\n");
564
            num++;
565
            sb.append(i);
566
            sb.append(' ');
567
            }
565 568
          }
566
        }
567 569

  
568
      android.util.Log.e("D", "numbers: "+sb);
570
        android.util.Log.e("D", "numbers: " + sb);
571
        }
569 572
      }
570 573
}
src/main/java/org/distorted/objectlib/tablebases/TablebasesCube2.java
18 18

  
19 19
///////////////////////////////////////////////////////////////////////////////////////////////////
20 20

  
21
public class TablebasesCube2 extends TablebasesMITM
21
public class TablebasesCube2 extends TablebasesPruning
22 22
{
23 23
  private static final int[][] P =
24 24
      {
......
73 73

  
74 74
  public TablebasesCube2(Resources res)
75 75
    {
76
    super(res, new int[] {R.raw.cube_2_pruning5,R.raw.cube_2_pruning11} );
76
    super(res, new int[] {R.raw.cube_2_pruning5}, new int[] {R.raw.cube_2_pruning11} );
77 77
    }
78 78

  
79 79
///////////////////////////////////////////////////////////////////////////////////////////////////
......
146 146

  
147 147
///////////////////////////////////////////////////////////////////////////////////////////////////
148 148

  
149
  int[] getPruningLevels()
149
  int[] getMidPruningLevels()
150 150
    {
151
    return new int[] {5,11};
151
    return new int[] {4,5};
152
    }
153

  
154
///////////////////////////////////////////////////////////////////////////////////////////////////
155

  
156
  int[] getHighPruningLevels()
157
    {
158
    return null;//new int[] {11};
159
    }
160

  
161
///////////////////////////////////////////////////////////////////////////////////////////////////
162

  
163
  int getGodsNumber()
164
    {
165
    return 11;
152 166
    }
153 167

  
154 168
///////////////////////////////////////////////////////////////////////////////////////////////////
src/main/java/org/distorted/objectlib/tablebases/TablebasesMITM.java
1
///////////////////////////////////////////////////////////////////////////////////////////////////
2
// Copyright 2023 Leszek Koltunski                                                               //
3
//                                                                                               //
4
// This file is part of Magic Cube.                                                              //
5
//                                                                                               //
6
// Magic Cube is proprietary software licensed under an EULA which you should have received      //
7
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //
8
///////////////////////////////////////////////////////////////////////////////////////////////////
9

  
10
package org.distorted.objectlib.tablebases;
11

  
12
import android.content.res.Resources;
13

  
14
import java.io.ByteArrayOutputStream;
15
import java.io.IOException;
16
import java.io.InputStream;
17

  
18
///////////////////////////////////////////////////////////////////////////////////////////////////
19

  
20
public abstract class TablebasesMITM extends TablebasesAbstract
21
{
22
  private PruningTable[] mTables;
23
  private boolean mInitialized;
24
  private int[] mLevels;
25

  
26
///////////////////////////////////////////////////////////////////////////////////////////////////
27

  
28
  abstract int[] getPruningLevels();
29

  
30
///////////////////////////////////////////////////////////////////////////////////////////////////
31

  
32
  private void createPruningTable(Resources res, int id, int index)
33
    {
34
    InputStream stream = res.openRawResource(id);
35
    ByteArrayOutputStream buffer = new ByteArrayOutputStream();
36

  
37
    int nRead;
38
    byte[] tmp = new byte[16384];
39

  
40
    try
41
      {
42
      while ((nRead = stream.read(tmp, 0, tmp.length)) != -1)
43
        {
44
        buffer.write(tmp, 0, nRead);
45
        }
46
      stream.close();
47
      byte[] data = buffer.toByteArray();
48
      buffer.close();
49
      mTables[index] = new PruningTable(data);
50
      mLevels[index] = mTables[index].getLevel();
51
      }
52
    catch(IOException ex)
53
      {
54
      mInitialized = false;
55
      }
56
    }
57

  
58
///////////////////////////////////////////////////////////////////////////////////////////////////
59

  
60
  public TablebasesMITM()
61
    {
62
    super();
63
    mInitialized = false;
64
    }
65

  
66
///////////////////////////////////////////////////////////////////////////////////////////////////
67

  
68
  public TablebasesMITM(Resources res, int[] resourceIDs)
69
    {
70
    super();
71

  
72
    int numOfIDs = resourceIDs.length;
73
    mTables = new PruningTable[numOfIDs];
74
    mLevels = new int[numOfIDs];
75
    mInitialized = true;
76

  
77
    for(int i=0; i<numOfIDs; i++) createPruningTable(res,resourceIDs[i],i);
78
    }
79

  
80
///////////////////////////////////////////////////////////////////////////////////////////////////
81

  
82
  public byte[][] getPacked()
83
    {
84
    if( !mInitialized )
85
      {
86
      int[] levels = getPruningLevels();
87
      int numLevels= levels.length;
88
      int maxLevel = 0;
89

  
90
      for( int l : levels )
91
        if( l>maxLevel ) maxLevel = l;
92

  
93
      createTablebase(maxLevel);
94
      mTables = new PruningTable[numLevels];
95
      mLevels = new int[numLevels];
96

  
97
      for(int i=0; i<numLevels; i++)
98
        {
99
        mTables[i] = new PruningTable(mTablebase,levels[i]);
100
        mLevels[i] = mTables[i].getLevel();
101
        }
102

  
103
      mInitialized = true;
104
      }
105

  
106
    int num = mTables.length;
107
    byte[][] data = new byte[num][];
108
    for(int i=0; i<num; i++) data[i] = mTables[i].getPacked();
109

  
110
    return data;
111
    }
112

  
113
///////////////////////////////////////////////////////////////////////////////////////////////////
114

  
115
  public int[][] solution(int index, int[] extra)
116
    {
117
    return null;
118
    }
119
}
src/main/java/org/distorted/objectlib/tablebases/TablebasesPruning.java
1
///////////////////////////////////////////////////////////////////////////////////////////////////
2
// Copyright 2023 Leszek Koltunski                                                               //
3
//                                                                                               //
4
// This file is part of Magic Cube.                                                              //
5
//                                                                                               //
6
// Magic Cube is proprietary software licensed under an EULA which you should have received      //
7
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html        //
8
///////////////////////////////////////////////////////////////////////////////////////////////////
9

  
10
package org.distorted.objectlib.tablebases;
11

  
12
import android.content.res.Resources;
13

  
14
import java.io.ByteArrayOutputStream;
15
import java.io.IOException;
16
import java.io.InputStream;
17

  
18
///////////////////////////////////////////////////////////////////////////////////////////////////
19

  
20
public abstract class TablebasesPruning extends TablebasesAbstract
21
{
22
  private boolean mInitialized;
23
  private PruningTable[] mHighTables;
24
  private PruningTable[] mMidTables;
25
  private int mGodsNumber, mLowestHigh, mHighestMid, mLowestMid;
26

  
27
///////////////////////////////////////////////////////////////////////////////////////////////////
28

  
29
  abstract int[] getMidPruningLevels();
30
  abstract int[] getHighPruningLevels();
31
  abstract int getGodsNumber();
32

  
33
///////////////////////////////////////////////////////////////////////////////////////////////////
34

  
35
  private PruningTable createPruningTable(Resources res, int id)
36
    {
37
    InputStream stream = res.openRawResource(id);
38
    ByteArrayOutputStream buffer = new ByteArrayOutputStream();
39

  
40
    int nRead;
41
    byte[] tmp = new byte[16384];
42

  
43
    try
44
      {
45
      while ((nRead = stream.read(tmp, 0, tmp.length)) != -1)
46
        {
47
        buffer.write(tmp, 0, nRead);
48
        }
49
      stream.close();
50
      byte[] data = buffer.toByteArray();
51
      buffer.close();
52
      return new PruningTable(data);
53
      }
54
    catch(IOException ex)
55
      {
56
      mInitialized = false;
57
      return null;
58
      }
59
    }
60

  
61
///////////////////////////////////////////////////////////////////////////////////////////////////
62

  
63
  public TablebasesPruning()
64
    {
65
    super();
66
    mGodsNumber = getGodsNumber();
67
    mInitialized = false;
68
    }
69

  
70
///////////////////////////////////////////////////////////////////////////////////////////////////
71

  
72
  public TablebasesPruning(Resources res, int[] midIDs, int[] highIDs)
73
    {
74
    super();
75

  
76
    int mid = midIDs !=null ? midIDs.length  : 0;
77
    int high= highIDs!=null ? highIDs.length : 0;
78

  
79
    mMidTables = mid >0 ? new PruningTable[mid] : null;
80
    mHighTables= high>0 ? new PruningTable[high]: null;
81
    mGodsNumber = getGodsNumber();
82
    mInitialized = true;
83

  
84
    for(int i=0; i<mid ; i++) mMidTables[i] = createPruningTable(res,midIDs[i] );
85
    for(int i=0; i<high; i++) mHighTables[i]= createPruningTable(res,highIDs[i]);
86
    }
87

  
88
///////////////////////////////////////////////////////////////////////////////////////////////////
89

  
90
  public byte[][] getPacked()
91
    {
92
    if( !mInitialized )
93
      {
94
      int[] midLevels = getMidPruningLevels();
95
      int numMidLevels= midLevels!=null ? midLevels.length : 0;
96
      int[] highLevels = getHighPruningLevels();
97
      int numHighLevels= highLevels!=null ? highLevels.length : 0;
98
      int maxLevel = 0;
99

  
100
      if( highLevels!=null )
101
        {
102
        for( int l : highLevels )
103
          if( l>maxLevel ) maxLevel = l;
104
        }
105
      else
106
        {
107
        if( midLevels!=null )
108
          for( int l : midLevels )
109
            if( l>maxLevel ) maxLevel = l;
110
        }
111

  
112
      createTablebase(maxLevel);
113
      mMidTables = numMidLevels >0 ? new PruningTable[numMidLevels ] : null;
114
      mHighTables= numHighLevels>0 ? new PruningTable[numHighLevels] : null;
115

  
116
      for(int i=0; i<numMidLevels; i++)
117
        mMidTables[i] = new PruningTable(mTablebase,midLevels[i]);
118
      for(int i=0; i<numHighLevels; i++)
119
        mHighTables[i] = new PruningTable(mTablebase,highLevels[i]);
120

  
121
      mInitialized = true;
122
      }
123

  
124
    int midNum  = mMidTables !=null ? mMidTables.length  : 0;
125
    int highNum = mHighTables!=null ? mHighTables.length : 0;
126
    byte[][] data = new byte[midNum+highNum][];
127

  
128
    for(int i=0; i<midNum ; i++) data[i       ] = mMidTables[i].getPacked();
129
    for(int i=0; i<highNum; i++) data[i+midNum] = mHighTables[i].getPacked();
130

  
131
    return data;
132
    }
133

  
134
///////////////////////////////////////////////////////////////////////////////////////////////////
135

  
136
  public int[][] solution(int index, int[] extra)
137
    {
138
    return null;
139
    }
140
}

Also available in: Unified diff