#include <linux/config.h>

#ifdef CONFIG_USB_DEBUG
#define DEBUG
#endif

#include <linux/usb.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/device.h>
#include <asm/byteorder.h>


#define USB_MAXALTSETTING               128     /* Hard limit */
#define USB_MAXENDPOINTS                30      /* Hard limit */

#define USB_MAXCONFIG                   8       /* Arbitrary limit */


static inline const char *plural(int n)
{
        return (n == 1 ? "" : "s");
}

static int find_next_descriptor(unsigned char *buffer, int size,
    int dt1, int dt2, int *num_skipped)
{
        struct usb_descriptor_header *h;
        int n = 0;
        unsigned char *buffer0 = buffer;

        /* Find the next descriptor of type dt1 or dt2 */
        while (size > 0) {
                h = (struct usb_descriptor_header *) buffer;
                if (h->bDescriptorType == dt1 || h->bDescriptorType == dt2)
                        break;
                buffer += h->bLength;
                size -= h->bLength;
                ++n;
        }

        /* Store the number of descriptors skipped and return the
         * number of bytes skipped */
        if (num_skipped)
                *num_skipped = n;
        return buffer - buffer0;
}

static int usb_parse_endpoint(struct device *ddev, int cfgno, int inum,
    int asnum, struct usb_host_interface *ifp, int num_ep,
    unsigned char *buffer, int size)
{
        unsigned char *buffer0 = buffer;
        struct usb_endpoint_descriptor *d;
        struct usb_host_endpoint *endpoint;
        int n, i;

        d = (struct usb_endpoint_descriptor *) buffer;
        buffer += d->bLength;
        size -= d->bLength;

        if (d->bLength >= USB_DT_ENDPOINT_AUDIO_SIZE)
                n = USB_DT_ENDPOINT_AUDIO_SIZE;
        else if (d->bLength >= USB_DT_ENDPOINT_SIZE)
                n = USB_DT_ENDPOINT_SIZE;
        else {
                dev_warn(ddev, "config %d interface %d altsetting %d has an "
                    "invalid endpoint descriptor of length %d, skipping\n",
                    cfgno, inum, asnum, d->bLength);
                goto skip_to_next_endpoint_or_interface_descriptor;
        }

        i = d->bEndpointAddress & ~USB_ENDPOINT_DIR_MASK;
        if (i >= 16 || i == 0) {
                dev_warn(ddev, "config %d interface %d altsetting %d has an "
                    "invalid endpoint with address 0x%X, skipping\n",
                    cfgno, inum, asnum, d->bEndpointAddress);
                goto skip_to_next_endpoint_or_interface_descriptor;
        }

        /* Only store as many endpoints as we have room for */
        if (ifp->desc.bNumEndpoints >= num_ep)
                goto skip_to_next_endpoint_or_interface_descriptor;

        endpoint = &ifp->endpoint[ifp->desc.bNumEndpoints];
        ++ifp->desc.bNumEndpoints;

        memcpy(&endpoint->desc, d, n);
        INIT_LIST_HEAD(&endpoint->urb_list);

        /* Skip over any Class Specific or Vendor Specific descriptors;
         * find the next endpoint or interface descriptor */
        endpoint->extra = buffer;
        i = find_next_descriptor(buffer, size, USB_DT_ENDPOINT,
            USB_DT_INTERFACE, &n);
        endpoint->extralen = i;
        if (n > 0)
                dev_dbg(ddev, "skipped %d descriptor%s after %s\n",
                    n, plural(n), "endpoint");
        return buffer - buffer0 + i;

skip_to_next_endpoint_or_interface_descriptor:
        i = find_next_descriptor(buffer, size, USB_DT_ENDPOINT,
            USB_DT_INTERFACE, NULL);
        return buffer - buffer0 + i;
}

void usb_release_interface_cache(struct kref *ref)
{
        struct usb_interface_cache *intfc = ref_to_usb_interface_cache(ref);
        int j;

        for (j = 0; j < intfc->num_altsetting; j++)
                kfree(intfc->altsetting[j].endpoint);
        kfree(intfc);
}

static int usb_parse_interface(struct device *ddev, int cfgno,
    struct usb_host_config *config, unsigned char *buffer, int size,
    u8 inums[], u8 nalts[])
{
        unsigned char *buffer0 = buffer;
        struct usb_interface_descriptor *d;
        int inum, asnum;
        struct usb_interface_cache *intfc;
        struct usb_host_interface *alt;
        int i, n;
        int len, retval;
        int num_ep, num_ep_orig;

        d = (struct usb_interface_descriptor *) buffer;
        buffer += d->bLength;
        size -= d->bLength;

        if (d->bLength < USB_DT_INTERFACE_SIZE)
                goto skip_to_next_interface_descriptor;

        /* Which interface entry is this? */
        intfc = NULL;
        inum = d->bInterfaceNumber;
        for (i = 0; i < config->desc.bNumInterfaces; ++i) {
                if (inums[i] == inum) {
                        intfc = config->intf_cache[i];
                        break;
                }
        }
        if (!intfc || intfc->num_altsetting >= nalts[i])
                goto skip_to_next_interface_descriptor;

        /* Check for duplicate altsetting entries */
        asnum = d->bAlternateSetting;
        for ((i = 0, alt = &intfc->altsetting[0]);
              i < intfc->num_altsetting;
             (++i, ++alt)) {
                if (alt->desc.bAlternateSetting == asnum) {
                        dev_warn(ddev, "Duplicate descriptor for config %d "
                            "interface %d altsetting %d, skipping\n",
                            cfgno, inum, asnum);
                        goto skip_to_next_interface_descriptor;
                }
        }

        ++intfc->num_altsetting;
        memcpy(&alt->desc, d, USB_DT_INTERFACE_SIZE);

        /* Skip over any Class Specific or Vendor Specific descriptors;
         * find the first endpoint or interface descriptor */
        alt->extra = buffer;
        i = find_next_descriptor(buffer, size, USB_DT_ENDPOINT,
            USB_DT_INTERFACE, &n);
        alt->extralen = i;
        if (n > 0)
                dev_dbg(ddev, "skipped %d descriptor%s after %s\n",
                    n, plural(n), "interface");
        buffer += i;
        size -= i;

        /* Allocate space for the right(?) number of endpoints */
        num_ep = num_ep_orig = alt->desc.bNumEndpoints;
        alt->desc.bNumEndpoints = 0;            // Use as a counter
        if (num_ep > USB_MAXENDPOINTS) {
                dev_warn(ddev, "too many endpoints for config %d interface %d "
                    "altsetting %d: %d, using maximum allowed: %d\n",
                    cfgno, inum, asnum, num_ep, USB_MAXENDPOINTS);
                num_ep = USB_MAXENDPOINTS;
        }

        len = sizeof(struct usb_host_endpoint) * num_ep;
        alt->endpoint = kmalloc(len, GFP_KERNEL);
        if (!alt->endpoint)
                return -ENOMEM;
        memset(alt->endpoint, 0, len);

        /* Parse all the endpoint descriptors */
        n = 0;
        while (size > 0) {
                if (((struct usb_descriptor_header *) buffer)->bDescriptorType
                     == USB_DT_INTERFACE)
                        break;
                retval = usb_parse_endpoint(ddev, cfgno, inum, asnum, alt,
                    num_ep, buffer, size);
                if (retval < 0)
                        return retval;
                ++n;

                buffer += retval;
                size -= retval;
        }

        if (n != num_ep_orig)
                dev_warn(ddev, "config %d interface %d altsetting %d has %d "
                    "endpoint descriptor%s, different from the interface "
                    "descriptor's value: %d\n",
                    cfgno, inum, asnum, n, plural(n), num_ep_orig);
        return buffer - buffer0;

skip_to_next_interface_descriptor:
        i = find_next_descriptor(buffer, size, USB_DT_INTERFACE,
            USB_DT_INTERFACE, NULL);
        return buffer - buffer0 + i;
}

int usb_parse_configuration(struct device *ddev, int cfgidx,
    struct usb_host_config *config, unsigned char *buffer, int size)
{
        unsigned char *buffer0 = buffer;
        int cfgno;
        int nintf, nintf_orig;
        int i, j, n;
        struct usb_interface_cache *intfc;
        unsigned char *buffer2;
        int size2;
        struct usb_descriptor_header *header;
        int len, retval;
        u8 inums[USB_MAXINTERFACES], nalts[USB_MAXINTERFACES];

        memcpy(&config->desc, buffer, USB_DT_CONFIG_SIZE);
        if (config->desc.bDescriptorType != USB_DT_CONFIG ||
            config->desc.bLength < USB_DT_CONFIG_SIZE) {
                dev_err(ddev, "invalid descriptor for config index %d: "
                    "type = 0x%X, length = %d\n", cfgidx,
                    config->desc.bDescriptorType, config->desc.bLength);
                return -EINVAL;
        }
        cfgno = config->desc.bConfigurationValue;

        buffer += config->desc.bLength;
        size -= config->desc.bLength;

        nintf = nintf_orig = config->desc.bNumInterfaces;
        if (nintf > USB_MAXINTERFACES) {
                dev_warn(ddev, "config %d has too many interfaces: %d, "
                    "using maximum allowed: %d\n",
                    cfgno, nintf, USB_MAXINTERFACES);
                nintf = USB_MAXINTERFACES;
        }

        /* Go through the descriptors, checking their length and counting the
         * number of altsettings for each interface */
        n = 0;
        for ((buffer2 = buffer, size2 = size);
              size2 > 0;
             (buffer2 += header->bLength, size2 -= header->bLength)) {

                if (size2 < sizeof(struct usb_descriptor_header)) {
                        dev_warn(ddev, "config %d descriptor has %d excess "
                            "byte%s, ignoring\n",
                            cfgno, size2, plural(size2));
                        break;
                }

                header = (struct usb_descriptor_header *) buffer2;
                if ((header->bLength > size2) || (header->bLength < 2)) {
                        dev_warn(ddev, "config %d has an invalid descriptor "
                            "of length %d, skipping remainder of the config\n",
                            cfgno, header->bLength);
                        break;
                }

                if (header->bDescriptorType == USB_DT_INTERFACE) {
                        struct usb_interface_descriptor *d;
                        int inum;

                        d = (struct usb_interface_descriptor *) header;
                        if (d->bLength < USB_DT_INTERFACE_SIZE) {
                                dev_warn(ddev, "config %d has an invalid "
                                    "interface descriptor of length %d, "
                                    "skipping\n", cfgno, d->bLength);
                                continue;
                        }

                        inum = d->bInterfaceNumber;
                        if (inum >= nintf_orig)
                                dev_warn(ddev, "config %d has an invalid "
                                    "interface number: %d but max is %d\n",
                                    cfgno, inum, nintf_orig - 1);

                        /* Have we already encountered this interface?
                         * Count its altsettings */
                        for (i = 0; i < n; ++i) {
                                if (inums[i] == inum)
                                        break;
                        }
                        if (i < n) {
                                if (nalts[i] < 255)
                                        ++nalts[i];
                        } else if (n < USB_MAXINTERFACES) {
                                inums[n] = inum;
                                nalts[n] = 1;
                                ++n;
                        }

                } else if (header->bDescriptorType == USB_DT_DEVICE ||
                            header->bDescriptorType == USB_DT_CONFIG)
                        dev_warn(ddev, "config %d contains an unexpected "
                            "descriptor of type 0x%X, skipping\n",
                            cfgno, header->bDescriptorType);

        }       /* for ((buffer2 = buffer, size2 = size); ...) */
        size = buffer2 - buffer;
        config->desc.wTotalLength = cpu_to_le16(buffer2 - buffer0);

        if (n != nintf)
                dev_warn(ddev, "config %d has %d interface%s, different from "
                    "the descriptor's value: %d\n",
                    cfgno, n, plural(n), nintf_orig);
        else if (n == 0)
                dev_warn(ddev, "config %d has no interfaces?\n", cfgno);
        config->desc.bNumInterfaces = nintf = n;

        /* Check for missing interface numbers */
        for (i = 0; i < nintf; ++i) {
                for (j = 0; j < nintf; ++j) {
                        if (inums[j] == i)
                                break;
                }
                if (j >= nintf)
                        dev_warn(ddev, "config %d has no interface number "
                            "%d\n", cfgno, i);
        }

        /* Allocate the usb_interface_caches and altsetting arrays */
        for (i = 0; i < nintf; ++i) {
                j = nalts[i];
                if (j > USB_MAXALTSETTING) {
                        dev_warn(ddev, "too many alternate settings for "
                            "config %d interface %d: %d, "
                            "using maximum allowed: %d\n",
                            cfgno, inums[i], j, USB_MAXALTSETTING);
                        nalts[i] = j = USB_MAXALTSETTING;
                }

                len = sizeof(*intfc) + sizeof(struct usb_host_interface) * j;
                config->intf_cache[i] = intfc = kmalloc(len, GFP_KERNEL);
                if (!intfc)
                        return -ENOMEM;
                memset(intfc, 0, len);
                kref_init(&intfc->ref);
        }

        /* Skip over any Class Specific or Vendor Specific descriptors;
         * find the first interface descriptor */
        config->extra = buffer;
        i = find_next_descriptor(buffer, size, USB_DT_INTERFACE,
            USB_DT_INTERFACE, &n);
        config->extralen = i;
        if (n > 0)
                dev_dbg(ddev, "skipped %d descriptor%s after %s\n",
                    n, plural(n), "configuration");
        buffer += i;
        size -= i;

        /* Parse all the interface/altsetting descriptors */
        while (size > 0) {
                retval = usb_parse_interface(ddev, cfgno, config,
                    buffer, size, inums, nalts);
                if (retval < 0)
                        return retval;

                buffer += retval;
                size -= retval;
        }

        /* Check for missing altsettings */
        for (i = 0; i < nintf; ++i) {
                intfc = config->intf_cache[i];
                for (j = 0; j < intfc->num_altsetting; ++j) {
                        for (n = 0; n < intfc->num_altsetting; ++n) {
                                if (intfc->altsetting[n].desc.
                                    bAlternateSetting == j)
                                        break;
                        }
                        if (n >= intfc->num_altsetting)
                                dev_warn(ddev, "config %d interface %d has no "
                                    "altsetting %d\n", cfgno, inums[i], j);
                }
        }

        return 0;
}

// hub-only!! ... and only exported for reset/reinit path.
// otherwise used internally on disconnect/destroy path
void usb_destroy_configuration(struct usb_device *dev)
{
        int c, i;

        if (!dev->config)
                return;

        if (dev->rawdescriptors) {
                for (i = 0; i < dev->descriptor.bNumConfigurations; i++)
                        kfree(dev->rawdescriptors[i]);

                kfree(dev->rawdescriptors);
                dev->rawdescriptors = NULL;
        }

        for (c = 0; c < dev->descriptor.bNumConfigurations; c++) {
                struct usb_host_config *cf = &dev->config[c];

                for (i = 0; i < cf->desc.bNumInterfaces; i++) {
                        if (cf->intf_cache[i])
                                kref_put(&cf->intf_cache[i]->ref, 
                                          usb_release_interface_cache);
                }
        }
        kfree(dev->config);
        dev->config = NULL;
}


// hub-only!! ... and only in reset path, or usb_new_device()
// (used by real hubs and virtual root hubs)
int usb_get_configuration(struct usb_device *dev)
{
        struct device *ddev = &dev->dev;
        int ncfg = dev->descriptor.bNumConfigurations;
        int result = -ENOMEM;
        unsigned int cfgno, length;
        unsigned char *buffer;
        unsigned char *bigbuffer;
        struct usb_config_descriptor *desc;

        if (ncfg > USB_MAXCONFIG) {
                dev_warn(ddev, "too many configurations: %d, "
                    "using maximum allowed: %d\n", ncfg, USB_MAXCONFIG);
                dev->descriptor.bNumConfigurations = ncfg = USB_MAXCONFIG;
        }

        if (ncfg < 1) {
                dev_err(ddev, "no configurations\n");
                return -EINVAL;
        }

        length = ncfg * sizeof(struct usb_host_config);
        dev->config = kmalloc(length, GFP_KERNEL);
        if (!dev->config)
                goto err2;
        memset(dev->config, 0, length);

        length = ncfg * sizeof(char *);
        dev->rawdescriptors = kmalloc(length, GFP_KERNEL);
        if (!dev->rawdescriptors)
                goto err2;
        memset(dev->rawdescriptors, 0, length);

        buffer = kmalloc(USB_DT_CONFIG_SIZE, GFP_KERNEL);
        if (!buffer)
                goto err2;
        desc = (struct usb_config_descriptor *)buffer;

        for (cfgno = 0; cfgno < ncfg; cfgno++) {
                /* We grab just the first descriptor so we know how long
                 * the whole configuration is */
                result = usb_get_descriptor(dev, USB_DT_CONFIG, cfgno,
                    buffer, USB_DT_CONFIG_SIZE);
                if (result < 0) {
                        dev_err(ddev, "unable to read config index %d "
                            "descriptor/%s\n", cfgno, "start");
                        goto err;
                } else if (result < 4) {
                        dev_err(ddev, "config index %d descriptor too short "
                            "(expected %i, got %i)\n", cfgno,
                            USB_DT_CONFIG_SIZE, result);
                        result = -EINVAL;
                        goto err;
                }
                length = max((int) le16_to_cpu(desc->wTotalLength),
                    USB_DT_CONFIG_SIZE);

                /* Now that we know the length, get the whole thing */
                bigbuffer = kmalloc(length, GFP_KERNEL);
                if (!bigbuffer) {
                        result = -ENOMEM;
                        goto err;
                }
                result = usb_get_descriptor(dev, USB_DT_CONFIG, cfgno,
                    bigbuffer, length);
                if (result < 0) {
                        dev_err(ddev, "unable to read config index %d "
                            "descriptor/%s\n", cfgno, "all");
                        kfree(bigbuffer);
                        goto err;
                }
                if (result < length) {
                        dev_warn(ddev, "config index %d descriptor too short "
                            "(expected %i, got %i)\n", cfgno, length, result);
                        length = result;
                }

                dev->rawdescriptors[cfgno] = bigbuffer;

                result = usb_parse_configuration(&dev->dev, cfgno,
                    &dev->config[cfgno], bigbuffer, length);
                if (result < 0) {
                        ++cfgno;
                        goto err;
                }
        }
        result = 0;

err:
        kfree(buffer);
        dev->descriptor.bNumConfigurations = cfgno;
err2:
        if (result == -ENOMEM)
                dev_err(ddev, "out of memory\n");
        return result;
}