Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • Will Tait: Check out this 2012 runescape video i did [link]
      July 18, 2019, 10:21:33 PM
    • Will Tait: Sorry to spam but
      July 18, 2019, 10:21:31 PM
    • hodford: generic-x . c0m is the best
      July 18, 2019, 02:32:34 AM
    • Cole1497: this shout box is diarrhetic
      July 15, 2019, 04:53:27 PM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 13, 2019, 04:54:43 PM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 13, 2019, 04:34:05 PM
    • rune-list:[link] RuneScape Private Servers List & Community.
      July 12, 2019, 12:25:23 AM
    • ragnoroker: Join PoonScape today! amazing new server - growing fast! [link]
      July 11, 2019, 10:31:15 AM
    • ragnoroker: Join PoonScape today! amazing new server - growing fast! [link]
      July 11, 2019, 10:31:11 AM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 10, 2019, 05:27:05 AM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 10, 2019, 05:10:40 AM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 10, 2019, 04:43:07 AM
    • ArtexAdv: Artex-rsps,com [link] (BRAND NEW SERVER)
      July 08, 2019, 07:59:48 PM
    • ArtexAdv:[link] (BRAND NEW SERVER)
      July 08, 2019, 07:59:31 PM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 08, 2019, 07:03:33 PM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 08, 2019, 07:03:16 PM
    • PavSwag: autoscape,0rg free ultra M box today (twisted bow??)
      July 08, 2019, 06:59:50 PM
    • dan v jad: guys join PkOwnage today!! Great new server, raids, eco, PK! Discord [link] homepage [link]
      July 07, 2019, 10:59:48 AM
    • ragnoroker: Join PoonScape today! amazing new server - growing fast! - [link]
      July 07, 2019, 08:19:24 AM
    • ragnoroker: Join PoonScape today! amazing new server - growing fast! - [link]
      July 07, 2019, 08:19:04 AM

    Author Topic: Virtual file cache indexing  (Read 2699 times)

    0 Members and 1 Guest are viewing this topic.

    Offline_nova

    • Member
    • **
    • Posts: 31
    • Thanks: +10/-10
      • View Profile
    Virtual file cache indexing
    « on: April 28, 2016, 04:32:57 AM »
    It's known that the Runescape cache structure has a single data file and a bunch of files which are pointers to the first chunk of a file, and the length of the file. The purpose of these file indexes is so that the client has O(1) lookup on entries on the cache, although the fact may not be apparent. In the newer engines which has a compressed container format, you actually can remove the need for a file index (unless you want to save memory) and build a virtual file index by analyzing the data file. Here's an implementation of that, just for the sake of an example.

    I think for any cache library, this is much easier in terms of dependencies (you only need a single class to read files) and it makes the file structure easier to understand. The catch is that you MUST have a container like format which describes the packed length of the data, but all the files are already packed that way.

    It's also important to note that chunk 0 is denoted as the 'EOF' chunk so you can estimate file sizes within a margin of 512 bytes. Depending on how large you cache archive is rebuilding the virtual index can take a longer amount of time to start up but you could precalculate the indexes (like the client already does) and load those files into memory.

    This solution also works better for knowing which files are corrupted, and what files are actually included in the cache.

    You don't have to use morton codes for hashing, I just did out of preference. You can just encode the cache id (or type) and file id into a dword.

    Code: Java
    1. packagecom.evelus.jagexfs;
    2.  
    3. importcom.evelus.jagexfs.util.MortonCode;
    4. importcom.google.common.base.Preconditions;
    5.  
    6. importjava.io.IOException;
    7. importjava.io.RandomAccessFile;
    8. importjava.nio.BufferUnderflowException;
    9. importjava.nio.ByteBuffer;
    10. importjava.util.HashMap;
    11. importjava.util.HashSet;
    12. importjava.util.Map;
    13. importjava.util.Set;
    14.  
    15. /**
    16.  * @author hadyn
    17.  */
    18. publicclass EntryCache {
    19.   privateRandomAccessFile data;
    20.   privatefinalbyte[] CHUNK_BUFFER =newbyte[EntryChunk.LENGTH];
    21.   private Map<Integer, CachePointer> pointers =new HashMap<>();
    22.  
    23.   publicstaticlong compressedLength = 0L;
    24.   publicstaticlong uncompressedLength = 0L;
    25.  
    26.   public EntryCache(RandomAccessFile data)throwsIOException{
    27.     this.data= data;
    28.     rebuildIndex();
    29.   }
    30.  
    31.   /**
    32.    * Reads an entry container from the cache and extracts the data.
    33.    *
    34.    * @param type    the type.
    35.    * @param entryId the entry id.
    36.    * @return the unpacked container bytes for the entry.
    37.    * @throws IOException if an I/O exception was encountered while reading the container.
    38.    */
    39.   publicbyte[] unpackContainer(int type, int entryId)throwsIOException{
    40.     byte[] bytes = readContainer(type, entryId);
    41.     Container container =newContainer();
    42.     container.read(ByteBuffer.wrap(bytes));
    43.     return container.getBytes();
    44.   }
    45.  
    46.   /**
    47.    * Reads an entry container from the cache. To extract the bytes from the container it will
    48.    * have to be unpacked.
    49.    *
    50.    * @param type    the type.
    51.    * @param entryId the entry id.
    52.    * @return the container bytes.
    53.    * @throws IOException if an I/O exception was encountered while reading the container.
    54.    *
    55.    * @see Container
    56.    */
    57.   publicbyte[] readContainer(int type, int entryId)throwsIOException{
    58.     if(!containsEntry(type, entryId)){
    59.       returnnull;
    60.     }
    61.     CachePointer pointer = pointers.get(MortonCode.mortonCode2i(type, entryId));
    62.     int length = pointer.getLength();
    63.     byte[] bytes =newbyte[length];
    64.     int chunkId = pointer.getFirstChunk();
    65.     EntryChunk chunk =new EntryChunk();
    66.     int destOff =0;
    67.     int part =0;
    68.     while(chunkId != EntryChunk.EOF_CHUNK){
    69.       readChunk(chunk, chunkId);
    70.       if(chunk.getType()!= type || chunk.getEntryId()!= entryId || part != chunk.getPart()){
    71.         thrownewIOException("Corrupted file: "+ type +", "+ entryId +".");
    72.       }
    73.       int read = length - destOff;
    74.       if(read > EntryChunk.DATA_LENGTH){
    75.         read = EntryChunk.DATA_LENGTH;
    76.       }
    77.       if(chunk.getLength()< read){
    78.         thrownew BufferUnderflowException();
    79.       }
    80.       System.arraycopy(chunk.getData(), 0, bytes, destOff, read);
    81.       chunkId = chunk.getNextChunk();
    82.       destOff += read;
    83.       part++;
    84.     }
    85.     return bytes;
    86.   }
    87.  
    88.   privatevoid readChunk(EntryChunk chunk, int chunkId)throwsIOException{
    89.     Preconditions.checkArgument(chunkId > EntryChunk.EOF_CHUNK, "Invalid chunk id: %s.", chunkId);
    90.     Preconditions.checkState(chunkExists(chunkId), "Chunk does not exist: %s.", chunkId);
    91.     long position = chunkId *(long) EntryChunk.LENGTH;
    92.     int len =(int)Math.min(data.length()- position, EntryChunk.LENGTH);
    93.     data.seek(position);
    94.     data.read(CHUNK_BUFFER, 0, len);
    95.     chunk.read(ByteBuffer.wrap(CHUNK_BUFFER));
    96.   }
    97.  
    98.   privatevoid writeChunk(EntryChunk chunk, int chunkId)throwsIOException{
    99.     ByteBuffer bb = ByteBuffer.wrap(CHUNK_BUFFER);
    100.     chunk.write(bb);
    101.     bb.flip();
    102.     bb.get(CHUNK_BUFFER, 0, bb.limit());
    103.     data.seek(chunkId *(long) EntryChunk.LENGTH);
    104.     data.write(CHUNK_BUFFER, 0, bb.limit());
    105.   }
    106.  
    107.   privateint getFreeChunk()throwsIOException{
    108.     return size()+1;
    109.   }
    110.  
    111.   privateboolean chunkExists(int chunkId)throwsIOException{
    112.     return size()> chunkId;
    113.   }
    114.  
    115.   publicboolean containsEntry(int type, int entryId){
    116.     return pointers.containsKey(MortonCode.mortonCode2i(type, entryId));
    117.   }
    118.  
    119.   /**
    120.    * Rebuilds the index for the cache. This function will clear any other file pointers already
    121.    * associated with this cache.
    122.    *
    123.    * @throws IllegalArgumentException if there are multiple chunks which describe the start of a
    124.    *                                  file.
    125.    */
    126.   publicvoid rebuildIndex()throwsIOException{
    127.     pointers.clear();
    128.  
    129.     Set<Integer> hashes =new HashSet<>();
    130.     EntryChunk chunk =new EntryChunk();
    131.     for(int chunkId =1; chunkId < size(); chunkId++){
    132.       readChunk(chunk, chunkId);
    133.       if(chunk.getPart()!=0){
    134.         continue;
    135.       }
    136.  
    137.       // Check to make sure that the start of a file isn't mentioned twice in the cache. If it is
    138.       // then we can't be sure which chunk is the actual start to the file.
    139.       int hash = MortonCode.mortonCode2i(chunk.getType(), chunk.getEntryId());
    140.       if(hashes.contains(hash)){
    141.         thrownewIllegalStateException(
    142.           "Found multiple chunks which describe the start of an entry; "+ chunk.getType()+
    143.             ", "+ chunk.getEntryId()+".");
    144.       }
    145.       hashes.add(hash);
    146.  
    147.       ByteBuffer bb = ByteBuffer.wrap(chunk.getData());
    148.       int compression = bb.get()& 0xff;
    149.       int packedLength = bb.getInt();
    150.  
    151.       compressedLength +=(long) packedLength;
    152.       if(compression !=Container.COMPRESSION_NONE){
    153.         if(chunk.getType()!=5){
    154.           uncompressedLength +=(long) bb.getInt(bb.position());
    155.         }
    156.       }else{
    157.         uncompressedLength +=(long) packedLength;
    158.       }
    159.  
    160.       // Calculate the length of the file from the container header. Table files are not stored
    161.       // with their version because they are internally defined in the format, every other file
    162.       // however is. The last two bytes of the file are reserved for the version.
    163.       int length = packedLength +Container.getHeaderLength(compression);
    164.       if(chunk.getType()!= EntryType.TYPE_TABLE){
    165.         length +=2;
    166.       }
    167.  
    168.       CachePointer pointer =new CachePointer(chunkId, length);
    169.       pointers.put(MortonCode.mortonCode2i(chunk.getType(), chunk.getEntryId()), pointer);
    170.     }
    171.   }
    172.  
    173.   /**
    174.    * Gets the volumes that are mentioned in all of the chunks.
    175.    *
    176.    * @return the volume ids.
    177.    * @throws IOException an I/O exception was encountered.
    178.    */
    179.   public Set<Integer> getMentionedTypes()throwsIOException{
    180.     Set<Integer> volumes =new HashSet<>();
    181.     EntryChunk chunk =new EntryChunk();
    182.     for(int chunkId =1; chunkId < size(); chunkId++){
    183.       readChunk(chunk, chunkId);
    184.       volumes.add(chunk.getType());
    185.     }
    186.     return volumes;
    187.   }
    188.  
    189.   /**
    190.    * Gets the size of the cache in chunks. The size takes into consideration the reserved EOF
    191.    * chunk so this function will always return a value equal to or greater than one.
    192.    *
    193.    * @return the size of the cache.
    194.    */
    195.   publicint size()throwsIOException{
    196.     return(int)(data.length()/ EntryChunk.LENGTH);
    197.   }
    198. }
    199.  
    200.  
    « Last Edit: April 28, 2016, 04:37:18 AM by _nova »
    Runescape Gambling

     

    Copyright © 2017 MoparScape. All rights reserved.
    Powered by SMFPacks SEO Pro Mod |
    SimplePortal 2.3.5 © 2008-2012, SimplePortal