Welcome to the Linux Foundation Forum!

exFat patent avoidance

SylviaElse
SylviaElse Posts: 3
edited November 2016 in Kernel Development

I've been looking at the patents that Microsoft holds on the exFat filesystem, to see whether they might be avoided, so that support could be included in Linux distributions. One, relating to hashes, https://www.google.com/patents/US8321439 seems quite straight forward, because it gives a specific way of calculating the hashes using rotations. I've created some code, included below, that shows that the same values can be calculated in a way that doesn't involve rotations, nor any operation that can be construed as a rotation.



Another patent https://www.google.com/patents/US8583708 deals with the structure of the file system. It's even more of junk patent than the first one, but be that as it may. An odd requirement in the claims is  "based on a determination that the critical primary directory entry is not recognized, preventing the volume from being mounted". It's difficult to see why that's in a claim at all, unless it was intended to disguise how little is being invented. Anyway, it seems to offer a way out - mount the volume anyway. Indeed it appears to me that the exfat-nofuse package actually does that.



There may be other patents that I'm not aware of.

#include <stdio.h>

#include <string.h>

#include <stdlib.h>



int main(int argc, char *argv[]) {

        if(argc < 2) {

                fprintf(stderr, "%s string\n", argv[0]);

                exit(1);

        }



        /* Microsoft patent algorithm */

        {

                unsigned char *cp = (unsigned char *) argv[1];



                unsigned x = 0;

                while(*cp) {

                        /* Do rotate. */

                        x = ((x & 1) << 31) + (x >> 1);



                        /* Add. */

                        x += *cp++;

                }

                printf("MS  value: %u\n", x);

        }



        /* Alternative algorigthm. */

        {

                unsigned rx;

                int i = 0;

                long long xl = 0;

                unsigned char *cp = (unsigned char *) argv[1];

                while(*cp) {

                        long long xc = ((long long) *cp++) << i;

                        long long av = ((xl & (1 << (i - 1))) << 32);

                        xl += av + xc;



                        i++;

                        if(i == 32) {

                                xl >>= 32;

                                i = 0;

                        }

                }



                rx = (unsigned) (xl >> (i - 1));



                printf("ALT value: %u\n", rx);

        }



        return 0;

}

 

 

Comments

  • SylviaElse
    SylviaElse Posts: 3
    edited November 2016

    The shift right some number of bits and add described in the claim is trivially different from the Buzhash.

    https://web.archive.org/web/19980211024140/http://serve.net/buz/Notes.1st.year/HTML/C6/rand.012.html

    which predates it. The claim relates to a rotate right of some number of bits, but that is always equivalent to a rotate left of some other number of bits. The described Buzhash involves a rotation left of one bit, so that's equivalent to a rotate right of 1 less than the number of bits being rotated. The claim uses addition rather than xor, but that is a small change.

     

     

     

  • saqman2060
    saqman2060 Posts: 777
    edited November 2016

    So you are saying you can add exFat support in the linux kernel that does no violate copyrights of exFat developed by microsoft? What benefits will an exFat filesystem bring to the Linux kernel?

Categories

Upcoming Training